CS 1102S - Data Structures and Algorithms, Semester 2 2009-2010

News
Brief Description and Topics
Textbook and Other Resources
Covered Material
Assignments
Lab tasks
More Module Information

News

Slides for Lecture 7 A are out, see below.

The calendar for the module is available below. Note the new deadline for Assignment 3: Friday, 5/3, 6:00pm.

This module is the second part of a two-part series on introductory programming from a functional paradigm. It emphasizes on algorithms, data structures, and software engineering. It also demonstrates programming language as an abstraction of computation by gradually revealing 'the details of computation': from a purely functional language transiting to an object-oriented paradigm of programming. Topics covered include: software engineering concepts, classic data structures (lists, stacks, queues, and their algorithmic designs), various forms of sorting methods, trees, BST, AVL tree, order property, hash tables, heap and priority queues, graphs representation and various graph-search algorithms, basic algorithmic analysis.

The topics will be covered in the following order:

Algorithm Analysis: Chapter 2 of textbook
Lists, Stacks and Queues: Chapter 3
Trees: Sections 4.1, 4.2, 4.3 (excluding 4.3.5) and 4.8
Hashing: Chapter 5
Priority Queues: Sections 6.1 to 6.4
Sorting: Sections 7.1 to 7.4 (excluding 7.4.1), 7.5, 7.6 (excluding 7.5.1), 7.7 (excluding "Average-case Analysis" in 7.7.5), 7.8
Graph Algorithms: Sections 9.1 to 9.3 (excluding 9.3.4, 9.3.5, 9.3.6), Section 9.4, Section 9.5.1, Section 9.7
Algorithm Design Techniques: Sections 10.1.1, 10.1.2, 10.2.1 (without proof), 10.2.2, 10.3.1, 10.3.3
External Algorithms: Sections 4.7, 7.10 (excluding 7.10.5 and 7.10.6)
Disjoint Sets: Chapter 8 (not covered in final exam)

Textbook and Other Resources

The textbook for the module is:

Data Structures and Algorithm Analysis in Java
Author:Mark Allen Weiss	2e / 2007
ISBN:0-321-37319-7	
Addison Wesley

See also the errata and the source code of programs for this book.

Resources for Java:

The Java Tutorials, especially Sections "Getting Started" and "Learning the Java Language"
Java Platform, Standard Edition 6 API Specification (including all Collection classes and interfaces)
Java Language Specification
Java Virtual Machine, Jon Meyer and Troy Downing, O'Reilly. The book is out of print; the first 10 chapters will be distributed in class.
Java Puzzlers: Traps, Pitfalls and Corner Cases, Joshua Bloch and Neal Gafter, Addison Wesley; puzzlers in the slides and assignments are from this book. Also note an entertaining (and instructional) YouTube video by one of the authors on a few puzzlers.
Eclipse tutorials:
- Basic tutorial
- General tutorials

Covered Material

The module material (slides, covered book chapters, etc) is accessible in the table below.

Lecture Date Subject Slides Notes

Lecture 01 A 13/1 Lecture 1: Intro to CS1102S Slides 01 A in color
Slides 01 A in B/W Sections 2.1 - 2.3 in textbook

CC 01 14/1 Crash Course 1: Recursion, Iteration, Lists Slides CC 01 in color
Slides CC 01 in B/W Programs for Crash Course 1
Lab instructions for Crash Course 1
Solutions for Crash Course 1

Lecture 01 B 15/1 Lecture 1 B: Algorithm Analysis II Slides 01 B in color
Slides 01 B in B/W Section 2.4 in textbook

CC 02 15/1 Crash Course 2: Loops and Arrays - Programs for Crash Course 2
Solutions for Crash Course 2

Lecture 02 A 20/1 Lecture 2 A: Objects, Classes Slides 02 A in color
Slides 02 A in B/W -

CC 03 21/1 Crash Course 3: Objects in Java Slides CC 03 in color
Slides CC 03 in B/W Programs for Crash Course 3
Lab instructions for Crash Course 3
Solutions for Crash Course 3

Lecture 02 B 22/1 Lecture 2 B: Java Virtual Machine Slides 02 B in color
Slides 02 B in B/W -

CC 04 22/1 Crash Course 4: Java Details Slides CC 04 in color
Slides CC 04 in B/W Lab instructions for Crash Course 4

Lecture 03 A 27/1 Lecture 3 A: Lists, Stacks, Queues I Slides 03 A in color
Slides 03 A in B/W Sections 3.1 to 3.3

Lecture 03 B 29/1 Lecture 3 B: Lists, Stacks, Queues II Slides 03 B in color
Slides 03 B in B/W Sections 3.4 and 3.5

Lecture 04 A 3/2 Lecture 4 A: Lists, Stacks, Queues III Slides 04 A in color
Slides 04 A in B/W Sections 3.6
Java programs Lecture 4 A

The Java Tutorials, Lesson: Generics

Lecture 04 B 5/2 Lecture 4 B: Lists, Stacks, Queues IV; Trees I Slides 04 B in color
Slides 04 B in B/W Section 3.7; Sections 4.1 and 4.2
Solution of Puzzler "Animal Farm"

Lecture 05 A 10/2 Lecture 5 A: Trees II Slides 05 A in color
Slides 05 A in B/W Sections 1.5.3, 1.5.5; Sections 4.3 and 4.8, excluding 4.3.5

Puzzler "Generic Drugs"

Lecture 05 B 12/2 Inner and Nested Classes Slides 05 B in color
(puzzlers)
Slides 05 B in B/W
(puzzlers) Solution of Midterm 1
Puzzler "Shades of Gray"

Recess Week 15 - 19/2 (no lectures) - -

Lecture 06 A 18/2 Lecture 6 A: Hashing Slides 06 A in color
Slides 06 A in B/W Sections 5.1 to 5.6
Puzzler "It's Elementary"

Lecture 06 B 26/2 Lecture 6 B: Priority Queues Slides 06 B in color
Slides 06 B in B/W Sections 6.1 to 6.4
Puzzler "The Last Laugh"

Lecture 07 A 3/3 Lecture 7 A: Sorting I Slides 07 A in color
Slides 07 A in B/W Sections 7.1 to 7.4, excluding 7.4.1

Lecture 07 B 5/3 Lecture 7 B: Sorting II Slides 07 B in color
Slides 07 B in B/W Sections 7.5 and 7.6, excluding 7.5.1

Lecture 08 A 10/3 Lecture 8 A: Sorting III Slides 08 A in color
Slides 08 A in B/W Sections 7.6 to 7.8, excluding "Average-case Analysis" in 7.7.5

Lecture 08 B 12/3 Midterm 2 not yet available Slides 08 B in color
Slides 08 B in B/W Solution of Midterm 2, AY 2008/2009 (note that in 2009, we covered AVL trees; this topic is not part of this year's module, so Questions 3 and 4 are not relevant)
Midterm 2, AY 2007/2008 (note that in 2008, the textbook was different; Questions 9-12 cover sorting, but different algorithms)

Lecture 09 A 17/3 Graph Algorithms I Slides 09 A in color
Slides 09 A in B/W Sections 9.1, 9.2, 9.3.1

Lecture 09 B 19/3 Graph Algorithms II Slides 09 B in color
Slides 09 B in B/W Section 9.3.2

Lecture 10 A 24/3 Graph Algorithms III Slides 10 A in color
Slides 10 A in B/W Correctness of Dijkstra's Algorithm (revisited)
Sections 9.3.3, 9.4 and 9.5.1

Lecture 10 B 26/3 Graph Algorithms IV Slides 10 B in color
Slides 10 B in B/W Sections 9.7 and 10.1.1

Lecture 11 31/3 Algorithm Design Techniques I Slides 11 A in color
Slides 11 A in B/W Sections 10.1.1, 10.1.2, 10.2.1 (without proof)

Lecture 12 A 7/4 Algorithm Design Techniques II Slides 12 A in color
Slides 12 A in B/W Sections 10.2.2, 10.3.1, 10.3.3

Lecture 12 B 9/4 Algorithm Design Techniques III; External Algorithms I Slides 12 A in color
Slides 12 A in B/W Sections 10.5, 4.7

Lecture 13 A 14/4 External Algorithms; Disjoint Sets Slides 13 A in color
Slides 13 A in B/W Sections 4.7, 7.10, Chapter 8

Lecture 13 B 16/4 Summary and Review of CS1102S Slides 13 B in color
Slides 13 B in B/W no new material covered

Lecture	Date	Subject	Slides	Notes
Lecture 01 A	13/1	Lecture 1: Intro to CS1102S	Slides 01 A in color Slides 01 A in B/W	Sections 2.1 - 2.3 in textbook
CC 01	14/1	Crash Course 1: Recursion, Iteration, Lists	Slides CC 01 in color Slides CC 01 in B/W	Programs for Crash Course 1 Lab instructions for Crash Course 1 Solutions for Crash Course 1
Lecture 01 B	15/1	Lecture 1 B: Algorithm Analysis II	Slides 01 B in color Slides 01 B in B/W	Section 2.4 in textbook
CC 02	15/1	Crash Course 2: Loops and Arrays	-	Programs for Crash Course 2 Solutions for Crash Course 2
Lecture 02 A	20/1	Lecture 2 A: Objects, Classes	Slides 02 A in color Slides 02 A in B/W	-
CC 03	21/1	Crash Course 3: Objects in Java	Slides CC 03 in color Slides CC 03 in B/W	Programs for Crash Course 3 Lab instructions for Crash Course 3 Solutions for Crash Course 3
Lecture 02 B	22/1	Lecture 2 B: Java Virtual Machine	Slides 02 B in color Slides 02 B in B/W	-
CC 04	22/1	Crash Course 4: Java Details	Slides CC 04 in color Slides CC 04 in B/W	Lab instructions for Crash Course 4
Lecture 03 A	27/1	Lecture 3 A: Lists, Stacks, Queues I	Slides 03 A in color Slides 03 A in B/W	Sections 3.1 to 3.3
Lecture 03 B	29/1	Lecture 3 B: Lists, Stacks, Queues II	Slides 03 B in color Slides 03 B in B/W	Sections 3.4 and 3.5
Lecture 04 A	3/2	Lecture 4 A: Lists, Stacks, Queues III	Slides 04 A in color Slides 04 A in B/W	Sections 3.6 Java programs Lecture 4 A The Java Tutorials, Lesson: Generics
Lecture 04 B	5/2	Lecture 4 B: Lists, Stacks, Queues IV; Trees I	Slides 04 B in color Slides 04 B in B/W	Section 3.7; Sections 4.1 and 4.2 Solution of Puzzler "Animal Farm"
Lecture 05 A	10/2	Lecture 5 A: Trees II	Slides 05 A in color Slides 05 A in B/W	Sections 1.5.3, 1.5.5; Sections 4.3 and 4.8, excluding 4.3.5 Puzzler "Generic Drugs"
Lecture 05 B	12/2	Inner and Nested Classes	Slides 05 B in color (puzzlers) Slides 05 B in B/W (puzzlers)	Solution of Midterm 1 Puzzler "Shades of Gray"
Recess Week	15 - 19/2	(no lectures)	-	-
Lecture 06 A	18/2	Lecture 6 A: Hashing	Slides 06 A in color Slides 06 A in B/W	Sections 5.1 to 5.6 Puzzler "It's Elementary"
Lecture 06 B	26/2	Lecture 6 B: Priority Queues	Slides 06 B in color Slides 06 B in B/W	Sections 6.1 to 6.4 Puzzler "The Last Laugh"
Lecture 07 A	3/3	Lecture 7 A: Sorting I	Slides 07 A in color Slides 07 A in B/W	Sections 7.1 to 7.4, excluding 7.4.1
Lecture 07 B	5/3	Lecture 7 B: Sorting II	Slides 07 B in color Slides 07 B in B/W	Sections 7.5 and 7.6, excluding 7.5.1
Lecture 08 A	10/3	Lecture 8 A: Sorting III	Slides 08 A in color Slides 08 A in B/W	Sections 7.6 to 7.8, excluding "Average-case Analysis" in 7.7.5
Lecture 08 B	12/3	Midterm 2	not yet available Slides 08 B in color Slides 08 B in B/W	Solution of Midterm 2, AY 2008/2009 (note that in 2009, we covered AVL trees; this topic is not part of this year's module, so Questions 3 and 4 are not relevant) Midterm 2, AY 2007/2008 (note that in 2008, the textbook was different; Questions 9-12 cover sorting, but different algorithms)
Lecture 09 A	17/3	Graph Algorithms I	Slides 09 A in color Slides 09 A in B/W	Sections 9.1, 9.2, 9.3.1
Lecture 09 B	19/3	Graph Algorithms II	Slides 09 B in color Slides 09 B in B/W	Section 9.3.2
Lecture 10 A	24/3	Graph Algorithms III	Slides 10 A in color Slides 10 A in B/W	Correctness of Dijkstra's Algorithm (revisited) Sections 9.3.3, 9.4 and 9.5.1
Lecture 10 B	26/3	Graph Algorithms IV	Slides 10 B in color Slides 10 B in B/W	Sections 9.7 and 10.1.1
Lecture 11	31/3	Algorithm Design Techniques I	Slides 11 A in color Slides 11 A in B/W	Sections 10.1.1, 10.1.2, 10.2.1 (without proof)
Lecture 12 A	7/4	Algorithm Design Techniques II	Slides 12 A in color Slides 12 A in B/W	Sections 10.2.2, 10.3.1, 10.3.3
Lecture 12 B	9/4	Algorithm Design Techniques III; External Algorithms I	Slides 12 A in color Slides 12 A in B/W	Sections 10.5, 4.7
Lecture 13 A	14/4	External Algorithms; Disjoint Sets	Slides 13 A in color Slides 13 A in B/W	Sections 4.7, 7.10, Chapter 8
Lecture 13 B	16/4	Summary and Review of CS1102S	Slides 13 B in color Slides 13 B in B/W	no new material covered

Assignments

Assignments are distributed online on this web site. Submission as indicated in the assignments. The solutions are discussed in the tutorial session after submission.

Assignment	Date handed out	Time due	Assignment Solution
Assignment 1 (Algorithm Analysis)	22/1/09	27/1, 6:00pm	Assignment 1 Solution Programs for Tutorial 1
Assignment 2 (Lists and Iteration)	3/2/10	9/2, 6:00pm	Assignment 2 Programs for Assignment 2 Solution for Assignment 2
Assignment 3 (Binary Heaps)	1/3/10	5/3, 6:00pm	Assignment 3 Programs for Assignment 3 Solution for Assignment 3
Assignment 4 (Sorting)	15/3/10	19/3, 6:00pm	Assignment 4 Programs for Assignment 4 Solution for Assignment 4
Assignment 5 (Graphs, Algorithm Design Techniques)	8/4/10	14/4, 6:00pm, submission on paper to COM1, 03-28	Assignment 5

Lab Tasks

Lab tasks are distributed online on this web site. No submission. The solutions are discussed in the lab sessions.

Lab Tasks Date handed out Lab session Solution

Sit-in Lab Tasks 1 (updated on 12/2) 1/2 1/2 Sit-in Lab Tasks 1 Solution

Lab Tasks 2
Programs for Lab Tasks 2 8/2 no submission not yet available

Sit-in Lab 2 22/2 22/2 solution for Groups 1 and 2
solution for Group 3

Lab 7 1/3 - Lab 7 description
Java code
solution for imbalance function

Lab 9 15/3 - Lab 9 description
Java code
solution for Lab 9

Lab 11 5/4 - Practice code for shortest path
The folder src\dijkstra contains two practice files graph1.txt and graph1.txt.
Note that you will need to configure Eclipse such that the file name is passed as argument:
Run: Run Configurations....: Arguments: Program arguments: "C:\...\dijkstra\src\graph1.txt"
Note that you will need the quotation marks and of course you will need to replace the ... by the correct path.

Lab 12 12/4 - Programs for Lab 12

More Module Information

Lectures

Lectures are taking place in COM1/206 on Wednesdays from 10am to noon and on Fridays from 11am to noon.

Mounting Information

Core module for students in the Bachelor of Computing programmes of the School of Computing

Modular credits: 5

Prerequisites: Pass CS 1101S

Workload

3-1-1-3-4

Explanation: A-B-C-D-E

A: no. of lecture hours per week

B: no. of tutorial hours per week

C: no. of lab hours per week

D: no. of hours for projects, assignments, fieldwork etc per week

E: no. of hours for preparatory work by a student per week

Assessment

6 assignments: due in weeks 3, 5, 7, 9, 11, 13: 12%

5 Lab tests (sit-in): labs of weeks 4, 6, 8, 10, 12): 20%

Midterm 1: MCQ, 10/2: 9%

Midterm 2: MCQ, 12/3: 9%

Final exam: 50%

Final Exam

Time: 3 MAY 2010 MORNING; place: to be announced
Final exam, AY 2008/2009 (includes solutions; note that last year, AVL trees were covered, see Question 4)
Final exam, AY 2007/2008 (includes some solutions; note that last year, the textbook was different)

Instructor

Martin Henz, consultation: Monday afternoon, 2-4; please drop an email to make sure he is available when you come.

Midterms

There will be two MCQ open book midterm exams:

Midterm Exam 1: February 10, 11:00AM, covering Java, Algorithm Analysis, and Lists, Stacks and Queues (textbook until page 100)
Midterm 1 (including solution)
Midterm 1 of last year
Some programs of Midterm 1 of last year
Midterm Exam 2: March 13, 11:00AM; covering:
- Trees: Sections 4.1 to 4.4 and 4.8, excluding 4.3.5
- Hashing: Sections 5.1 to 5.6
- Priority Queues: Sections 6.1 to 6.4
- Sorting: Sections 7.1 to 7.5, excluding 7.4.1 and 7.5.1
Midterm 2
Midterm 2 Solution

Martin Henz

Lab Tasks	Date handed out	Lab session	Solution
Sit-in Lab Tasks 1 (updated on 12/2)	1/2	1/2	Sit-in Lab Tasks 1 Solution
Lab Tasks 2 Programs for Lab Tasks 2	8/2	no submission	not yet available
Sit-in Lab 2	22/2	22/2	solution for Groups 1 and 2 solution for Group 3
Lab 7	1/3	-	Lab 7 description Java code solution for imbalance function
Lab 9	15/3	-	Lab 9 description Java code solution for Lab 9
Lab 11	5/4	-	Practice code for shortest path The folder `src\dijkstra` contains two practice files `graph1.txt` and `graph1.txt`. Note that you will need to configure Eclipse such that the file name is passed as argument: Run: Run Configurations....: Arguments: Program arguments: "C:\...\dijkstra\src\graph1.txt" Note that you will need the quotation marks and of course you will need to replace the ... by the correct path.
Lab 12	12/4	-	Programs for Lab 12