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.
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.
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 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
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 9: Guis
Lecture Tree Searching
Lectures 12: Graphs
Lecture 13: Greedy Algorithms
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
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
Week 3 Priority Queues & Hashing
Heaps, array representations, collisions
|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|
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|