ICS 311: Algorithms, Main Portal Page, TuTh Section 003
Last revised 2019-10-1
Fall, 2019
Instructor: Prof. Lee Altenberg
Class Meetings: SECTION 003 Tuesday/Thursday 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:
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).
(Note that the exact Topics, Problem Sets, and may exam dates may change as needed.)
Schedule:
Week 1: Introduction to Course, Basic Concepts
- Tue. 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).
- Thu. 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
Week 3: Growth of Functions and Asymptotic Concepts
- Tue. 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).
- Thu. Week 3 - #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).
Week 4: Analysis of Basic Data Structures, Probabilistic Analysis, Randomization, Skip Lists
Week 5: Hash Tables, Divide and Conquer, Recurrences
- Tue. 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).
- Thu. Week 5 - #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).
Week 6: Binary Search Trees, Advanced Sorts and Queues (Heaps, Priority Queues, Heapsort)
- Tue. 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)
- Thu. Week 6 - #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
Week 7: Midterm 1
- Tue. Week 7. Review for Midterm 1.
- Thu. Week 7, Oct. 10 - Midterm 1, Topics 1-8, in Webster 101 as usual!
Week 8: Theoretical Limits, and O(n) Sorts
- Tue. 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)
- Thu. 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
- Tue. 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;
- Thu. 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: Dynamic Programming and Greedy Algorithms
- Tue. 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)
- Thu. 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
- Tue. 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;
- Thu. 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: Amortized Analysis, Sets and Union-Find and Minimum Spanning Trees
- November 11 (Mon) Holiday observed: Veteran's Day (non-instructional day)
- Tue. 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;
- Thu. 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).
Week 13: - #18 - Single-Source Shortest Paths
Week 14: Midterm 2
- Tue. Week 14, Nov. 26 - Midterm 2: Topics 9-17, in Webster 101 as usual!
- November 28 (Th) Holiday: Thanksgiving Day (non-instructional day)
- November 29 (F) (non-instructional day)
Week 15:
- Tue. Week 15 - #20 - Maximum Flow:
CLRS Sections 26.1-26.3;
Topic 20 Notes;
screencasts 20* on Laulima and YouTube:
20A,
20B, and
20C;
- Thu. Week 15 - #24 - Complexity Theory & NP-Completeness:
CLRS Chapter 35;
Topic 24 Notes;
screencasts 24* on Laulima and YouTube:
24A,
24B, and
24C;
not covered in MIT video lectures.
Week 16: Approximation Algorithms, String Matching
Finals Week:
Created by Dan Suthers
modified by Jan Stelovsky
modified by Lee Altenberg
