ICS 311 Spring 2015 Index
This is an index of web pages for ICS 311 Algorithms, taught Spring 2015 by
Nodari Sitchinava,
with a closely related section taught by Dan Suthers.
Generally the course is run within Laulima. Notes and other
material are posted on this site,
http://www2.hawaii.edu/~nodari/teaching/s15/, and on YouTube. However, course participants
will need to log into Laulima regularly to watch screencasts, take quizzes, submit assignments, and
to use other facilities such as discussions and the mail tool as needed. Classes are in Webster 101
Contents
- Schedule: A weekly listing of events (includes lecture notes,
problem sets, projects, and exams).
- Syllabus: Overview of course and plan.
- Topics: Summary of weekly topics.
- Problem Sets: List of active and planned problem sets.
- Exams: Planned exam dates
This is not a complete schedule: see the Schedule for that. Dates
vary between this section and Prof. Sitchinava's section. CLRS is the Cormen Leiserson Rivest and
Stein textbook. Topic numbers are not in sequence due to changes to the curriculum since 2014.
- 01/13 - #1 - Introduction to Course: CLRS Chapter 1;
Topic 01 Notes
- 01/15 & 20 - #2 - Examples of Analysis with Insertion and Merge Sort: CLRS Chapter 2;
Topic 02 Notes
- 01/22 - #2.5 - Review of Proof Techniques : Review of select topics from ICS 141/241. Material is posted in Laulima (in Wiki, under "Topic 02.5")
- 01/27 - #3 - Growth of Functions and Asymptotic Concepts:
CLRS Chapter 3; Topic 03 Notes
- 01/29 - #4 - Basic ADTs (Stacks, Queues, Lists and Trees):
CLRS Chapter 10; Topic 04 Notes
- 02/03 - #7 - Divide & Conquer and Analysis of Recurrences:
CLRS Chapter 4 (4.1 & 4.3-4.5); Topic 07 Notes
- 02/05 - #8 - Binary Search Trees: CLRS Sections 12.1-12.3 (skim 12.4);
Topic 08 Notes
- 02/10 - #9 - Heaps, Heapsort and Priority Queues: CLRS Chapter 6 (all);
Topic 09 Notes
- 02/12 - #5 - Quicksort, Probabilistic Analysis and Randomized Algorithms:
CLRS Sections 5.1-5.3, CLRS Chapter 7 (all);
Topic 05 Notes
- 02/17 - #10a - Selection and Order Statistics: CLRS Chapters 9;
- 02/19 - #10b - Theoretical Limits, and O(n) Sorts: CLRS Chapters 8;
Topic 10 Notes
- 02/24 - #6 - Hash Tables: CLRS Sections 11.1-11.4;
Topic 06 Notes
- 02/26 - #11 - Balanced Trees (2-3-4 and Red-Black):
Sedgewick Chapter 15 & CLRS Chapter 13;
Topic 11 Notes
- 03/05 - #12 - Dynamic Programming:
CLRS Chapter 15 (and optionally Sedgewick Chapter 37);
Topic 12 Notes
- 03/12 - #13 - Greedy Algorithms & Huffman Codes:
CLRS Sections 16.1-16.3;
Topic 13 Notes
- 03/17-19 - #14 - Graph Representations and Basic Algorithms:
CLRS Chapter 22; Goodrich & Tamassia excerpt on Representations;
Optionally Newman (2010) chapter 9 in Laulima;
Topic 14 Notes
- 03/31 - #15 - Amortized Analysis:
CLRS Chapter 17;
Topic 15 Notes (leave out the Potential method), AND:
- 03/31 - #16 - Sets and Union-Find:
CLRS Sections 21.1-21.3 and Theorem 21.14;
Topic 16 Notes (leave out the linked representation)
- 04/02 - #17 - Minimum Spanning Trees:
CLRS Chapter 23;
Topic 17 Notes
- 04/07 - #18 - Single-Source Shortest Paths:
CLRS Sections 24.1-24.3;
Topic 18 Notes
- 04/09 - #19 - All-Pairs Shortest Paths:
CLRS Chapter 25;
Topic 19 Notes
- 04/14 - #20 - Maximum Flow:
CLRS Sections 26.1-26.3;
Topic 20 Notes
- 04/16 - #22 - Multithreading CLRS Chapter 27 (emphasis on sections 27.1 and 27.3);
Topic 22 Notes
- 04/23 - #24 - Complexity Theory & NP-Completeness:
CLRS Chapter 34;
Topic 24 Notes (no homework)
- 04/30 - #25 - Approximation Algorithms:
CLRS Chapter 35;
Topic 25 Notes (no homework)
- 05/05 - Special Topics (brief introductions, no homework)
potentially including the following and to presented by guest speakers where possible
- String Matching:
CLRS Chapter 32 (emphasis on sections 32.1 and 32.3);
Topic 23 Notes
- Public Key Encryption:
CLRS Chapter 31 (emphasis on 31.7)
The problems are being revised for Spring 2015, and will be released in Laulima when ready.
- Problem Set #0
A practice problem on Topic 1, not graded
- Problem Set #1
(Topic 2) due 23:55 (11:55 pm) Tuesday January 27th
- Problem Set #2
(Topics 3 & 4) due 23:55 (11:55 pm) Tuesday February 3rd
- Problem Set #3
(Topics 7 & 8) due 23:55 (11:55 pm) Tuesday February 10th
- Problem Set #4
(Topics 9 & 5) due 23:55 (11:55 pm) Tuesday February 17th
- Problem Set #5
(Topic 10a & 10b) due 23:55 (11:55 pm) Tuesday February 24th
- Problem Set #6
(Topics 6 & 11) due 23:55 (11:55 pm) Tuesday March 10th
- Problem Set #7
(Topics 12 & 13) due 23:55 (11:55 pm) Tuesday March 17th
- Problem Set #8
(Topics 14) due 23:55 (11:55 pm) Tuesday March 31st
- Problem Set #9
(Topic 15, 16 & 17) due 23:55 (11:55 pm) Tuesday April 7th
- Problem Set #10
(Topic 18 & 19) due 23:55 (11:55 pm) Tuesday April 14th
- Problem Set #11
Extra credit (Topic 20 & 22) due 23:55 (11:55 pm) Tuesday April 28th
- 03/03: Midterm 1 - Topics 1-10 excluding 6, in Webster 101
- 04/21: Midterm 2 - Topics 6, 11-19, in Webster 101
- 05/14 9:45-11:45am: Final Exam: Cumulative on all topics (1-20, 22, 24, & 25) excluding those by invited
faculty, in Webster 101
Nodari Sitchinava (based on material by Dan Suthers)
Last modified: Thu Apr 25 16:00:56 HST 2015
