Spring 2011 Syllabus

- MW 10:30-11:50 am; final exam Friday May 13, 10:00 am - 12:45 pm
- TR 12:00-1:20 pm; final exam Tuesday May 10, 1:00 - 3:45 pm.

You should be enrolled in one lab section. You must attend the lecture section and the lab section that you are enrolled in; do not drop in on another lab section without prior approval.

NOTE: The next computer science class CS 2402 (Data Structures) has two prerequisites: CS2401 and MATH 2300 (Discrete Math). To avoid delaying your progress through the program, if you are not currently taking MATH 2300 and have not already passed it, you should seriously consider adjusting your schedule.

**Instructors:**

- Vladik Kreinovich, vladik@utep.edu,
office phone (915) 747-6951, teaches MW section

Office hours: MW 10-10:30 am, MW 12-12:30 pm, MW 1-1:30 pm, MW 3-3:30 pm, or by appointment,

in COMP 215. - David Novick,
novick@utep.edu,
office phone (915) 747-6031, teaches TR section

Office hours: Tu 10:00-11:30 am, Fr 1:30-3:00 pm, or by appointment,

in COMP 203.

**Teaching Assistants (TAs):**

- Neith Estrada, email naestrada2@miners.utep.edu

teaches MW 10:30-11:50 am, TR 12:00-1:20 pm, and TR 4:30-5:50 pm labs

office hours T 5-7 pm or by appointment, in CS 300. - Alexis Hernandez, email jahernandez6@miners.utep.edu

teaches MW 3-4:20 pm and TR 3-4:20 pm labs

office hours TR 2-3 pm, in COMP 304.

**Peer Leaders:**

- Eva Gabriela Del Toro, email egdeltoro2010@gmail.com
- Ricardo Nunez, email rnunez7@miners.utep.edu
- Alexandra Rebollosa, email sarebollosamuqiz@miners.utep.edu

**Course Objectives:**
This is the second course for students majoring in Computer Science. Students
will learn about fundamental computing algorithms, including searching and
sorting; elementary abstract data types including linked lists, stacks, queues
and trees; and elementary algorithm analysis. Prerequisite: CS 1401, with a
grade of C or better.

**Knowledge and Abilities Required Before the Students Enter the Course:**
Students are assumed
to be comfortable programming in Java. Students should be able to code basic
arithmetic expressions, define simple classes, use strings, code loops and
conditional statements, write methods, create objects from classes, invoke
methods on an object, perform basic text file input and output, and use
arrays.

**Learning Outcomes**

**Level 3: Synthesis and Evaluation:**

Level 3 outcomes are those in which the student can apply the material in new
situations. This is the highest level of mastery. On successful completion of
this course, students will be able to identify, implement and use the following
data structures as appropriate for a given problem:

- multi-dimensional arrays;
- lists implemented as arrays or linked lists;
- stacks;
- queues;
- binary trees and binary search trees;
- simple hashes.

**Level 2: Application and Analysis:**

Level 2 outcomes are those in which the student can apply the material in
familiar situations, e.g., can work a problem of familiar structure with minor
changes in the details. Upon successful completion of this course, students
will be able to:

- use Big-O notation to express the best-, average- and worst-case behaviors of an algorithm;
- explain the structure and use of activation records;
- determine the best, average and worst-case behaviors of an algorithm;
- assess time and space trade-offs in algorithms;
- explain, code, and use quadratic and O(n log n) sorting algorithms;
- implement recursive algorithms over natural numbers, lists, and trees;
- define and use classes, subclasses and inheritance;
- implement a simple graphical user interface;
- perform string manipulation and simple parsing;
- implement and use multidimensional arrays;
- describe the importance of encapsulation and information hiding;
- implement applications and simulations of the data structures identified above;
- implement simple sequential and binary search algorithms;
- implement quadratic sorting algorithms;
- describe memory allocation of integers, real numbers, arrays and objects.

**Level 1: Knowledge and Comprehension**

Level 1 outcomes are those in which the student has been exposed to the terms
and concepts at a basic level and can supply basic definitions. On successful
completion of this course, students will be able to:

- explain basic and introductory-level notions of a virtual machine;
- explain the concept of polymorphism;
- use class browsers and related tools;
- identify class hierarchies;
- recognize the basic terms associated with particular data structures, for example, head/tail, push/pop/peek

**Textbook:**
Reading and laboratory assignments will be drawn from *Data Structures and
Problem Solving using Java* by M. A. Weiss.
If necessary, this book is available at the
bookstore and through major online book retailers, and you are expected to
acquire a copy for your use in this course. Photocopied textbooks are
illegal and their use will not be tolerated.

**Software:**
Software used in this course will be available on the Windows computers in
the main lab (room 300) and in the two instructional labs (rooms 301 and
319). For those who wish to use the course software on your home computer,
instructions will be given in the labs.

**Assignments:**
Reading and homework assignments will be handed out or announced in class
and in labs. If you miss a class or lab session, it is your responsibility
to find out what you missed. You should expect to spend at least 8
hours/week outside of class and lab on reading and homework.

**Grading:**
Your semester grade will be based on a combination of homework and lab
assignments, weekly quizzes, lab attendance, exams, and a final exam. The
approximate percentages are as follows:

- 30% Homework and lab assignments
- 5% Lab attendance
- 10% In-class exercises and quizzes
- 30% Exams (3 exams, 10 points each)
- 25% Final comprehensive exam

**Homework and Lab Assignments:**
Homework and lab
assignments are designed to allow you to practice using the
concepts presented in lecture and in your reading. Homework and lab
assignments may
include written problems, tutorial exercises, and programming problems.
Assignments usually will be due at the start of your lab session. Late
homework will be accepted only in unusual circumstances, by prior
arrangement if at all possible.

Homework must be done individually. While you may discuss the problem in
general terms with other people, your answers and your code should be
written and tested by you alone. **Do not exchange programs or let someone
look at your code, even "just so they can see how you did it."**
If you need
help, consult a TA, a peer leader, or a professors

**Laboratory Sessions:**
Laboratory sessions are designed to give you guidance in getting your
homework assignment started well. In a typical lab session, the Teaching
Assistant will present additional material that will help you complete the
assignment and answer your questions as you begin work.

You are required to sign up for and attend one of the lab sections associated with this course. Each lab section meets two or three times a week for a total of 3 hours per week. Attendance will be taken. To earn full credit for attendance, you must show up on time, stay for the entire session, and work only on your assignment. You may be excused from lab with full credit if your work has been completed and turned in.

In addition to turning in your lab assignment, you must schedule a one-on-one lab demo session with your TA in which you will explain how your program works and he/she will ask questions to test your understanding of the program being submitted. The TA will then assign a pass/fail grade for this session; a student receiving a failing grade in this session will receive a grade of zero for the lab assignment. NOTE: The lab demo should be presented before or on the deadline for the assignment.

Late Projects: Lab projects up to a week late will receive up to 70% percent of full credit, from one to two weeks late, up to 50%, and more than two weeks late will receive no credit. NOTE: The turn-in-date for labs is not when you e-mail the code, but the date when you demo the lab.

Guidelines for grading labs are listed here.

**You must score 60% or better on the lab assignments to pass this
course.**

**Quizzes:**
The purpose of a quiz is to ensure that you have read the weekly
reading assignment and to verify that you have mastered the major concepts
of recent lectures. Quizzes typically will be about 5-15 minutes in length and
will cover the material assigned to be read for the upcoming lecture plus
selected concepts from previous lectures.
There will be no make-up on missed quizzes.

**Exams:**
The purpose of the exams is to allow you to demonstrate mastery of course
concepts. Each exam will focus on the material from the previous three or
four weeks. Exams will take place during the regular class session. There
will be three exams, each contributing 10% to your final grade, or 30% total
to the overall course grade.

Because the exams contribute so heavily to your total grade, it is vital that you do well on them. If you have test-taking difficulties in general, or if you have difficulties with our tests in particular, please come talk to us as soon as possible (and certainly before the first exam).

Exams are planned for the following dates (subject to change):

- Wednesday, February 16 or Thursday, February 17 (Week 5)
- Tuesday, March 29 or Wednesday, March 30 (Week 10)
- Wednesday, April 27 or Thursday, April 28 (Week 14)

**Final Exam:**
The final exam will be comprehensive and will count 25% toward your course
grade.
If you cannot demonstrate your understanding of the concepts and skills
needed for success in CS 2402, you cannot pass this course even if you have
enough points to do so.

You must take the final exam during the time shown in the schedule for the class section that you are formally enrolled in. Do not simply "drop in" to the other section; there will not be a copy of the exam for you. This is University policy. If you have a scheduling conflict (e.g., if you are taking a final at EPCC) or if you are scheduled for three final exams in one day, see one of the instructors IN ADVANCE.

**Grading:**
The nominal percentage-score-to-letter-grade conversion is as follows:

- 90% or higher is an A
- 80-89% is a B
- 70-79% is a C
- 60-69% is a D
- below 60% is an F

**Standards of Conduct:**
You are expected to conduct yourself in a professional and courteous manner, as
prescribed by the
UTEP Standards
of Conduct.

Graded work, e.g., homework and tests, is to be completed independently and should be unmistakably your own work (or, in the case of group work, your team's work), although you may discuss your project with other students in a general way. You may not represent as your own work material that is transcribed or copied from another person, book, or any other source, e.g., a web page.

Academic dishonesty includes but is not limited to cheating, plagiarism and collusion.

- Cheating may involve copying from or providing information to another student, possessing unauthorized materials during a test, or falsifying data (for example program outputs) in laboratory reports.
- Plagiarism occurs when someone represents the work or ideas of another person as his/her own.
- Collusion involves collaborating with another person to commit an academically dishonest act.

**Disabilities:**
If you feel that you may have a disability that requires accommodation,
contact the Disabled Student Services Office at 747-5184, go to Room 106E
Union, or email dss@utep.edu

**Weekly Schedule:** (tentative and subject to change) When learning a new
topic, often, we will see how it relates to the previously learned topics
and thus, we will use this as an opportunity to recall
the previous topics

- Reading: Section 2.4, Arrays
- January 18-21: class overview, arrays

- Reading: Chapter 2.4, Arrays
- January 24-28: multi-dimensional arrays

- Reading: Chapter 5, Algorithm Analysis
- January 31 - February 4: algorithm analysis, search algorithms

- Reading: Sections 6.1, 6.5-6.6, ADT, Lists, Stacks, and Queues
- February 7-11: abstract data types, linked lists, first introduction to stacks and queues

- Reading: no specific reading
- February 14-18: Review, Exam 1

- Reading: Chapter 7, Recursion
- February 21-25: recursion

- Reading: Chapter 7, Recursion
- February 28 - March 4: recursion

- Reading: Chapter 8, Sorting
- March 7-11: sorting

- Reading: Chapter 11, Stacks and Compilers
- March 21-25: stacks and elementary compilers

- Reading: no specific reading
- March 28 - April 1: Review, Exam 2

- Reading: Chapter 16, Stacks and Queues
- April 4-8: stacks and queues

- Reading: Sections 19.1-19.4, Binary Search Trees
- April 11-15: binary search trees

- Reading: Chapter 21, Heaps and heapsort
- April 18-22: heaps and heapsort

- Reading: Sections 20.1-20.2, 20.6, Hash Tables
- April 25-29: hash tables, reviews for Exam 3, Exam 3

- Reading: no specific reading
- May 2-5: hash tables, review of Exam 3, review for the final exam