ICS23: Data Structures and Algorithms

A collaborative problem-solving approach

Course Goals

Using the Java language students will learn the properties and implementation details of the fundamental data structures (arrays, lists, queues, stacks, dictionaries, hashtables, trees, graphs) that often are at the heart of any program. Students will also learn basic problem solving methods, such as divide and conquer, separate and conquer, dynamic programming, greedy algorithms, tree and search algorithms as well as some useful applications. As part of the coding assigments, students will be expected to analyse their code and follow good object-oriented design.

Grading

There will be four programming assignments, 4 quizzes and a final. The course is not graded on a curve. Roughly the homeworks count 40%, the quizzes 20%, and the final 40%. I don't use a formula to assign grades. Trends matter. You need to pass both the homeworks and the final to pass the class. The lowest quiz score will be dropped. If you can't make a quiz, then that quiz is the one that is dropped. The coding assignments will be in Java. Roughly, the exams and homeworks will count equally. The final exam will be based on the text, lecture notes, and homeworks. Each chapter ends with a summary. Be sure that you know every concept discussed in the summary. The fastest way to get questions answered is to email either the TAs or me. Answers of general interest will be posted on the bulletin board (ics.23). You may also use the bulletin board to ask classmates for appropriate help. Any form of inappropriate help will result in an F grade in the class and a letter in your file. If you are unsure whether the type of help you are seeking is appropriate, imagine that you are video taped and the tape was shown to me.

The homeworks focus on using arrays, lists, trees, hashing, and sorting.

Grades are posted at: http://www.ics.uci.edu/~javid/ICS23/grades.htm.

Knowledge Prerequisites

You should be familiar with arrays, linked lists, and (unbalanced) binary trees. By familiar I mean that you have implemented these data structures and are confident with dealing with them. Additional you should have the a rudimentary knowledge of O-notation, in particular the ability to analyze programs that involve multiple loops, but not programs that involve recursion. It is also expected that you are familiar with Java, but not with Gui interfaces. My experience is that students who know C++ can learn enought of Java in just a few hours to write programs required for this class.

Text

Text Data Structures and Problem Solving using Java by Mark Allen Weiss


Suggested for those interested in GUI's: : UP to speed in Swing by Steven Gutz

Web Course Resources

Lecture notes for the Java Language are available on-line Java Notes . Please tell me if you find any errors or misrepresentations.

Li Zhang has lab notes on course at www.ags.uci.edu/~lzhang

Class lectures notes are available at \\masterhit\instructional\ics-23\Files. Click on network neighborhood to get to masterhit.

Current class questions/answer are put on the newsgroup bulletin board ics23.

Note: Questions asked after 4pm on Friday are not guaranteed to be answered. Sometimes I take the weekends off.

Note: Because of time constraints in the summer, no understanding of proofs will be necessary. They are in the notes for those who are interested.

Lecture 1 Design

Lecture 2 Analysis

Lecture 3 Data Structure Overview

Lecture 4: Trees

Lecture 5: Compression

Lecture 6: Priority Queues

Lecture 7: Hashing

Lecture 8:Recursion

Lecture 9: Guis

Lecture 10&11:Sorting

Lecture Tree Searching

Lectures 12: Graphs

Lecture 13: Greedy Algorithms

Computer Resources

Everyone needs to have an ICS computer account in order to access Masterhit and Visual Cafe. You can get this account in the main computer room, 364.

Lab 364 Summer Hours:

Monday - Sunday 10 - 6pm

Tests

Quizzes: Every Monday (Homeworks due on Monday also)


(except Sept 3, when quiz and homework due date is Sept 5)


Final: Sept 12 1:00- 3:50 same room as lecture

Lecture Schedule

Week 1 Design and analysis, O notation, Linked Lists, Collections
Collections: Arrays, Lists, Trees, Queues, HashTables
Week 2 Binary trees, Balanced Trees, Huffman Trees
Tree Search, rotations, expected cost

Week 3 Priority Queues & Hashing

Heaps, array representations, collisions

Week4 Sorting

Insertion, QuickSort, MergeSort, Radix Sorting, BubbleSort
Week 5 Holiday + Graphs
Representations, basic algorithms: Kruskal's, Prim's and Dijsktra's algorithm, topological sorting:
Week 6 Greedy Algorithms + Final
Local Improvement, Simulated Annealing, Branch and Bound

You should know the complexity of the algorithms/methods that we have covered in class. You should also understand how the algorithms work and be able to illustrate what they do. For example, given a specific binary tree you should be able to show the changes in the tree that would remove a specific element.


Monday Lectures Wednesday Lectures Homework: Due Monday
8/6: OOD+Complexity Analysis

Chapter 5: key pages 107-112, 121-122, 128-129. Some of 437-447		 8/10: Linked List, Stack,Queue, Collections

Chapter 6: all of it		 Cache as a List, Array, and Binary Tree.
8/13:Binary Trees+Balanced Trees

Quiz on Complexity		 8/15: Huffman Trees + Start PQs Huffman code for text
8/20: Priority Queues and Hashing

Quiz on Trees and Huffman Codes		 8/22: Recursion + Gui's Surprising Kmers
8/27: Sorting

Quiz on PQs & Hashing & Recursion		 8/29: Tree Search + Graphs Experimental Comparison of sorting
9/3: Holiday 9/5: Graphs/ Quiz on Sorting  
9/10: Greedy Algorithms 9/12: FINAL Exam