CS 105 Introduction to Data Structures and Algorithms 2nd Semester, 2005-2006 John Paul Vergara, PhD

Syllabus

Announcements

• Final written homework due Monday, March 20. Submit through moodle using a .txt or .doc file.
• Using the map shown in section 12.5 (p. 626) in the textbook, find shortest paths from LAX to all other cities. For each city, provide the length of the shortest path and the sequence of vertices that yields the shortest path.
• Exercise R-12.17, p. 650. A bridge is determined by a pair of islands. Return the sequence of bridges (pairs of island numbers) in the order they were selected using Kruskal's algorithm.
• Deadline for project 2 moved to Friday, March 10. Those who submit by midnight March 8 get a 5-point bonus. Output files are ready (use the following cellphone numbers file :
• Deadline for project 2 moved to Wednesday, March 8.
• Sample input files for project 2: input file 1 , input file 2 . Come up with your own cell phone number file--that should be easy.
• Project 2 draft specs ready (due March 6). Keep posted for sample files.
• Lab for today, 10 Feb 2006 (you may work in pairs): Implement a priority queue using an array (employ any of the two list strategies discussed). Download this zip file and complete it by adding your priority queue implementation. The test program is called TestPQ.java. Make sure to revise PQFactory.java so that you indicate the class name of the priority queue that you develop. Also, you write your name(s) on the priority queue class before you submit.
• No classes on Wednesday, 1 February, the day after the midterm.
• Midterm exam coverage: all material up to Recursion.
• Project 1 clarification: arrange it so that CQSimulation takes the input file name as its argument. For example, java CQSimulation simple.txt
• Midterm exam on Jan 31, 6-8pm. Room assignments:
Section A (Vergara): CTC 103
Section B (Vergara): CTC 106
Section C (Amarra): CTC 301
Section D (Amarra): CTC 304
• Specs for your first programming project due Friday, January 27 : sample input files- test file 1 (updated!)   [output] , test file 2   [output] .
• Lab for Friday (13 Jan): Complete the following Snake program present in most cellphones. It requires a NodeQueue class to run; You may work in pairs. The lab is due today at the end of the class period (or as specified by your instructor). Lab is worth 20 points, an additional 2 points if you also include and implement an ArrayQueue class; check your work by updating QueueFactory. Submit through Moodle .
• In the homework, we forgot to include array accesses in the enumeration of operations to count. You may or may not include these operations: we will consider both resulting answers correct.
• Homework 1 due Dec 21, midnight, through moodle (submit as .txt, .doc, .pdf, or .jpg; zipped if more than 1 file), or by 5pm through the department secretary, if handwritten.
• For Nov 18-25: Read Chapter 3 of the textbook.
• Welcome to this website! Visit this link regularly for course material, announcements and updates