Class Meetings: SECTION 002 Monday/Wednesday 6-7:40 pm Webster 101

Teaching Assistant: David Luis dluis@hawaii.edu, Office Hours: 303-2 POST, Tues 4:30-5:30pm, Wed 1:30-2:30pm

Learning Assistant: Matthew Lam mwklam@hawaii.edu, Office Hours: 318A POST, Mon. 4:30-6pm, Tues. 6-7pm.

• Catalog description: Design and correctness of algorithms, including divide-and-conquer, greedy and dynamic programming methods. Complexity analyses using recurrence relations, probabilistic methods, and NP-completeness. Applications to order statistics, disjoint sets, B-trees and balanced trees, graphs, network flows, and string matching.
• Prerequisites: ICS 211: Data Structures, and ICS 241: Discrete Mathematics for Computer Science II, or consent.

Student Outcomes:

• SO #1: Analyze a complex computing problem and apply principles of computing and other relevant disciplines to identify solutions.

Resources:

Textbooks:

• Required: Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. [CLRS], 2009. Introduction to Algorithms. 3rd Edition. MIT press. Cambridge, MA.
• Supplementary: Goodrich, M.T., Tamassia, R. and Goldwasser, M.H., 2014. Data Structures and Algorithms in Java. John Wiley & Sons.
• Supplementary: Sedgewick, Robert, 1983. Algorithms (Addison-Wesley series in computer science).

Online:

This is the portal page for ICS 311 Algorithms taught by Prof. Lee Altenberg. This is the root page to access the other online resources:

• This website
• Laulima: Individual Homework Assignments, Grade records, Forums, e-mail tool
• YouTube: Prof. Suthers's videos, UHMICSAlgorithms
• Google Drive folders : Class Problem Google Docs

Notes and other material for this course are posted on this site, i.e., https://dynamics.org/ICS/311/, and on YouTube. However, you as a course participant will need to log into Laulima regularly to submit assignments, and to use other facilities such as discussions and the mail tool as needed. Also, you will need to take peers' quizzes, and once you took such a peer quiz evaluate it and you will get a chance to improve the quiz or agree with an improvement already made or with the original.

EXTRA CREDIT: In addition, we have prepared for you a "One Idea Every Day" Google Sheet (under Google Drive > Shared with me) where you should post one idea every day (or at least every workday).

Syllabus

(Note that the exact Topics, Problem Sets, and may exam dates may change as needed.)

• General Course Information
• Topic Overview
• Format
• Screencasts and Online Lectures
• Assessment (Grading)
• Policies

Schedule:

Week 1: Introduction to Course, Basic Concepts

• Mon. Week 1 - #0 - Course Orientation. Prof. Stelovsky introduces extra credit opportunities: 'Flip-Flop': Making and taking peer quizzes; One-Idea-Every-Day App. Algebra "Boot Camp" Quiz (not graded).
  
• Wed. Week 1 - #1 - Introduction to Algorithms:
  Study resources include CLRS Chapter 1; Topic 01 Notes; Abstract Data Types video
  Practice Quiz #00 given in class (and on future days for every numbered topic). (Not graded and not included in course grade: it's for practice).

Week 2: Continuing Basic Concepts

• September 2 (Mon) Holiday: Labor Day (non-instructional day)
• September 3: 4pm:
  • Payment Receipt Deadline for transactions completed August 20 to September 3
  • Last day to register/add courses/change grading options
  • Last day for 100 percent tuition refund
• Wed. Week 2 - #2 - Examples of Analysis with Insertion Sort:
  Study resources include CLRS Chapter 2 sections 2.1 and 2.2; Topic 02 Notes up through "Worst Case Rate of Growth"; screencasts 02A-C (up through "Detailed Analysis of Insertion Sort") on YouTube: 2A, 2B, and 2C; MIT Lecture 01
  Quiz on Topic 02a given in class

Week 3: Growth of Functions and Asymptotic Concepts

• Mon. Week 3 - #2 cont. - Examples of Analysis with Merge Sort:
  Rest of CLRS Chapter 2; rest of Topic 02 Notes; screencasts 02D and 02E on YouTube: 2D and 2E;
  Quiz on Topic 02b given in class

  NOTE: Every class meeting will have a quiz drawn from the assigned TOPIC NOTES. We omit explicit mention of the quizzes from here on.

Video: Introduction to Algorithms by Stanford University courseera: Lecture 1
• Wed. Week 3 - #3 - Growth of Functions and Asymptotic Concepts:
  CLRS Chapter 3; Topic 03 Notes ; screencasts 03*, henceforth available on YouTube: 3A, 3B, 3C, and 3D; MIT Lecture 02 (beginning-16:50).

Week 4: Analysis of Basic Data Structures, Probabilistic Analysis, Randomization, Skip Lists

• Mon. Week 4 - #4 - Basic ADTs (Stacks, Queues, Lists and Trees):
  CLRS Chapter 10; Topic 04 Notes; screencasts 04* on YouTube: 4A and 4B; (not covered in MIT video lectures).
• Wed. Week 4 - #5 - Probabilistic Analysis and Randomized Algorithms; Skip Lists:
  CLRS Sections 5.1-5.3 and 5.4.1; Goodrich & Tamassia section (On Laulima under [Resources] -> [Goodrich & Tamassia]); Topic 05 Notes; screencasts on YouTube: 5A, 5B, 5C, and 5D; MIT Lecture on Skip Lists

Week 5: Hash Tables, Divide and Conquer, Recurrences

• Mon. Week 5 - #6 - Hash Tables:
  CLRS Sections 11.1-11.4; Topic 06 Notes; screencasts on YouTube: 6A, 6B, 6C, and 6D; MIT Lecture 07 and MIT Lecture 08 (see notes for guide to what parts to attend to)
• Wed. Week 5 - #7 - Divide & Conquer and Analysis of Recurrences:
  CLRS Sections 4.1 & 4.3-4.5; Topic 07 Notes; screencasts 07* on YouTube: 7A, 7B, 7C, and 7D; MIT Lecture 02 (16:51-end) and MIT Lecture 03 (through about 13:07: we don't cover Strassen or Fibonacci numbers).

Week 6: Binary Search Trees, Advanced Sorts and Queues (Heaps, Priority Queues, Heapsort)

• Mon. Week 6 - #8 - Binary Search Trees:
  CLRS Sections 12.1-12.3 (see also Theorem 12.4); Topic 08 Notes; screencasts 08* on YouTube: 8A, 8B, 8C, and 8D; (No corresponding MIT lecture identified).
• Wed. Week 6 - #9 - Heap, Heapsort and Priority Queues:
  CLRS Chapter 6 (all); Topic 09 Notes; screencasts on YouTube: 9A, 9B, 9C, and 9D; (no corresponding MIT lecture identified)

Week 7: Quicksort, Midterm 1

• Mon. Week 7 - #10A - Quicksort:
  CLRS Chapter 7 (Chapter 8 is in notes but will be continued on Wednesday); Topic 10 Notes; screencasts on YouTube: 10A and 10B; MIT Lecture 04
• Wed. Week 7, Oct. 9 - Midterm 1, Topics 1-8, in Webster 101 as usual!

Week 8:Theoretical Limits, and O(n) Sorts

• Mon. Week 8 - #10B- Theoretical Limits, and O(n) Sorts:
  CLRS Chapter 8; Topic 10 Notes; screencast on YouTube: 10C; MIT Lecture 05 (but we don't go into as much detail)
• - Wed. Week 8 - #11A - Balanced Trees (2-3-4 Trees, Red-Black Trees 1):
  Sedgewick Chapter 15 & CLRS Chapter 13 (Read Sedgewick first to understand the 2-4 tree and how a RBT is a representation of a 2-4 tree. Allow extra time for this material!); Topic 11 Notes; screencasts 11* on Laulima and YouTube: 11A, 11B, 11C, and 11D; MIT Lecture 10.

Week 9: Balanced Trees, Dynamic Programming

• Mon. Week 9 - #11B - Balanced Trees (Red-Black Trees 2):
  Sedgewick Chapter 15 & CLRS Chapter 13; Topic 11 Notes; screencasts 11* on Laulima and YouTube: 11A, 11B, 11C, and 11D;
• Wed. Week 9 - #12 - Dynamic Programming:
  CLRS Chapter 15 (and optionally Sedgewick Chapter 37); Topic 12 Notes; screencasts 12* on Laulima and YouTube: 12A, 12B, 12C, and 12D; MIT Lecture 15

Week 10: Greedy Algorithms

• Mon. Week 10 - #13 - Greedy Algorithms & Huffman Codes:
  CLRS Sections 16.1-16.3; Topic 13 Notes; screencasts 13* on Laulima and YouTube: 13A, 13B, and 13C; (MIT Lecture 16: only briefly mentioned at 48:16)
• Wed. Week 10 - #14A - Graph Representations and Breadth-First Search:
  CLRS 22.1-22.2; Goodrich & Tamassia section on Graph Representations in Laulima; Optionally Newman (2010) chapter 9 in Laulima; Topic 14 Notes; screencasts 14A-C on Laulima and YouTube: 14A, 14B, and 14C; MIT Lecture 16 (just the first few minutes for graph representations; the rest focuses on MST).
  

Week 11: Graph Representations, Breadth-First, Depth-First Search, Topological Sort, and Strongly Connected Components

• Mon. Week 11 - #14B - Depth-First Search, Topological Sort, and Strongly Connected Components:
  CLRS 22.3-22.5; screencasts 14D-F on Laulima and YouTube: Topic 14 Notes; 14D, 14E, and 14F;
• Wed. Week 11 - #15 - Amortized Analysis:
  CLRS 17.1-17.2; Topic 15 Notes (skip Potential Method) & screencasts 15* on Laulima and YouTube: 15A, 15B, and MIT Lecture 13

Week 12: Sets and Union-Find and Minimum Spanning Trees

• November 11 (Mon) Holiday observed: Veteran's Day (non-instructional day)
• Wed. Week 12 - #16 - Sets and Union-Find:
  CLRS 21.1, & 21.3; Also see Lemma 21.11, 21.12, 21.13 and Theorem 21.14; Topic 16 Notes (skip Linked List representation: Forest is much better); screencasts 16 on Laulima and YouTube: 16A;

Week 13: -

• Mon. Week 12 - #17 - Minimum Spanning Trees:
  CLRS Chapter 23; Topic 17 Notes; screencasts 17* on Laulima and YouTube: 17A, 17B, and 17C; MIT Lecture 16 (second part).
• Wed. Week 13 - - Single-Source Shortest Paths:
  CLRS Sections 24.1-24.3; Topic 18 Notes; screencasts 18* on Laulima and YouTube: 18A, 18B, and 18C; MIT Lecture 17, MIT Lecture 18 (first half)

Week 14: All-Pairs Shortest Paths and Maximum Flow in Graphs

• Mon. Week 14 - November 25, Midterm 2: Topics 9-17, in Webster 101 as usual!
• Wed. Week 14 - #19 - All-Pairs Shortest Paths:
  CLRS Chapter 25; Topic 19 Notes; screencasts 19* on Laulima and YouTube: 19A, 19B, and 19C; MIT Lecture 19