- Professor:
*Dennis Kibler**kibler@ics.uci.edu* - Class Meetings: 1:00- 3:50 Mondays &Wednesdays (Social Science Plaza A Rm 1100)
- Office Hours: 4-5 Mondays,Wednesdays (414D ICS)
- Teaching Assistants:
*Li Zhang*(lzhang1@ics.uci.edu),*Javid Huseynov*(javid@ics.uci.edu) - Tutor: Chang (Charles) Liu (liu@ics.uci.edu) Office hours: MW 8-11; T/Ths 8-12 ICS2: Rm 249
- Discussions: 1:00-2:50 Tues/Thurs in ICS 183, 189, 192

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 3 Data Structure Overview

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

**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-4478/10: Linked List, Stack,Queue, Collections

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

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

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

Quiz on PQs & Hashing & Recursion8/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**