Introduction to Data Structures and Algorithms

Second Semester, 2019/2020

Prescription

This course builds on COMP 102, focusing on the techniques for designing, building and analysing computer programs that deal with large collections of data. The course addresses techniques for programming with collections of data, and the data structures and algorithms needed to implement these collections. The course expands programming skills and provides an understanding of the principles of data abstraction, algorithm design, and the analysis of algorithms fundamental to computer science.

Learning Objectives

Students who pass this course will be able to:
  1. read and write programs using standard collections (sets, lists, bags, stacks, queues, priority queues, maps)
  2. read and write programs using linked data structures, particularly tree structures
  3. read and write programs using recursion
  4. understand ideas of algorithm complexity, do an approximate analysis of simple programs with collections, and make efficient design decisions
  5. recognise, understand and use a selection of basic algorithms

Staff

The staff for the course are

Course Organisation details

Dates, Times, and Rooms: Lectures and Laboratories

Due to the COVID-19 (novel coronavirus), there will be online lectures during the semester. There will also be helpdesk sessions.

You will be provided with recorded lectures every week. We will also have online sessions through DingTalk, Tencent Meeting, WeChat and TeamViewer.

The course will have lectures on Mondays 14:20 to 15:55 and Thursdays 16:15 to 17:50.

A schedule of lecture topics and assignment dates is on the website. Copies of the lecture slides will be available online, and may also be distributed at the lectures.

We will run online Help Desks sessions where you can ask additional questions and get help on your homework assignments.

Students will be able to ask for help on problems with code, via an online help system.

Textbook and other Materials

The optional textbook for COMP 103 is:

  • Lewis, DePasquale and Chase, "Java Foundations: Introduction to Program Design and Data Structures", preferably 4th edition, though earlier editions will still be helpful.

You may choose to find additional resources, either printed books or web resources, that provide more background on programming in Java. You will find some of the resources on the course website at http://ecs.victoria.ac.nz/Courses/XMUT102_2019T2

Workload

The course is expected to have a total workload of about 150 hours. If you are still struggling with English, you may need to spend more time than this. This means you should expect to work on this course for about 10 hours every week.

Assignments and Practical Work.

There will be frequent programming exercises as part of the course. These will consist of very small programs to ensure you understand how to use the key new programming constructs introduced in the lectures. You will generally work on these in small groups, to get to know other students who you can study with and develop your collaboration skills.

There will be 6 programming homework assignments throughout the course. Each assignment includes one or two homework programs that you must complete and submit. The descriptions of the assignments will be made available online. Most of the assignments contain three parts:
  1. A Core part, which you should aim to start in the lab, and involves constructing programs using the basic concepts and constructs,
  2. A Completion part, which extends the Core part and involves more difficult problem solving and may cover additional concepts and constructs,
  3. A Challenge part, which usually involves substantially more difficult programming and may require you to find out new concepts and constructs by yourself.

The Core part will be worth 70% of the assignment, the Completion part will be worth 20%, and the Challenge part will be worth 10%. The programs will be marked primarily on whether they work correctly, but there will be some weighting for good design.

We expect all students to be able to complete most of the Core part, and at least attempt the Completion part. The Completion part is important for students planning to go on to. The Challenge components are for students aiming for a high grade. If it takes you more than about 6 hours to complete the Core part of an assignment, we suggest that you should not spend additional time on the Challenge part. It is probably better to spend the additional time going over your notes from the lectures, going to the office hours, or working on questions and problems with other students.

Assignment Submission

When you have completed them, the assignments must be submitted electronically. You will need to submit your java files by uploading them to a web page: https://ecs.wgtn.ac.nz/Courses/XMUT103_2020T1/Assignments.

Marks and comments will be returned through the ECS marking system, also available through the course web pages.

Assignment Marking and Late Penalties

The assignments are very important for your learning, and will together contribute a total of 24% to your final grade.

We will mark the assignments as quickly as possible.

A mandatory course requirement is that you must submit reasonable attempts for at least 5 out of the 6 assignments (or obtain an exemption from the Course Coordinator).

If you miss an assignment, contact the lecturer as soon as possible. Students who have missed an assignment without an acceptable excuse will be required to do make-up programming assignments in order to be able to pass the course.

Late Penalties

LATE DAY POLICY (for Assignments). Each student will have TWO LATE DAY which you may choose to use for any assignment or assignments during the course. Please note that these 48 hours are for the whole course, not for each assignment. So you have on average 8 late hours for each assignment. There will be no penalty applied for these hours. You do not need to apply for them, instead any late hours you have left will be automatically applied to assignments that you submit late. You get zero marks for late assignments when you run out of these late hours, unless you have made arrangements on the basis of exceptional circumstances with the course coordinator.

Working Together.

Assignments MUST be done individually

Make sure you read the section on plagiarism below.

Tests and Exam

There will be one mid-semester test worth 20% held during the course.

You should contact the lecturer as early as possible if you are not going to be able to attend a test at the scheduled time, or if you missed a test.

There will be an exam at the end of the course.

All the assessment (assignments, tests, and exam) will address the learning objective of the course - reading, comprehending, designing, and writing programs in an object-oriented style. The tests and exam will assess all the material covered by the course up to the time of the test/exam.

Grade Computation

Your grade for the course will be based on a combined mark for the assignments, the tests, and the exam:

Item Weight
Assignments 1-6 24% (4% each)
Test #1 20%
 
Examination 56%

If you get a higher mark in the exam than you did in a test, then we will increase your mark for the test up to your exam mark.

Grading

A 100-95 A- 94-90
B+ 89-87 B 86-83 B- 82-80
C+ 79-77 C 76-73 C- 72-70
D+ 69-67 D 66-63 D- 62-60
F 59 or lower

Academic Integrity and Plagiarism.

Academic integrity means that university staff and students, in their teaching and learning, are expected to treat others honestly, fairly and with respect at all times. It is not acceptable to mistreat academic, intellectual or creative work that has been done by other people by representing it as your own original work. Academic integrity is important because it is the core value on which the University's learning, teaching and research activities are based. The University's reputation for academic integrity adds value to your qualification. Plagiarism is presenting someone else's work as if it were your own, whether you mean to or not. "Someone else's work" means anything that is not your own idea. Even if it is presented in your own style, you must acknowledge your sources fully and appropriately. This includes:
  • Material from books, journals or any other printed source
  • The work of other students or staff
  • Information from the internet
  • Software programs and other electronic material
  • Designs and ideas
  • The organisation or structuring of any such material

Notes

You should always properly cite any work of others that you are including in work that you submit.

Do not lend your work to others. If someone submits work that is the same as or very similar to yours you should expect to be asked to explain and, if the explanation is not satisfactory, to get zero.

If you are ever in doubt as to whether some action you have taken may be considered as plagiarism, you should consult your lecturer and/or clearly state on the submitted work the extent of the contribution from others.
  • Do not give your answers to other students – you may get zero!
  • If you copy another student’s work (assignment/test/final exam), you will get zero.
  • Do not ask other students for their answers – it is stealing their marks.

Plagiarism and Code

If you are completing a programming project, you may be allowed to use code segments from a software library on the web, from model solutions in previous courses you have taken, or even from other students. If you do this, you must clearly indicate all of the code that has come from another source and state the source. Unless your course requirements state otherwise, you are not required to cite algorithms, data structures or source code provided with the assignment or from lecture notes. If you are in doubt about the use of code that you have not written yourself you should check with your lecturer before submitting the program. If you have had help from someone else (other than a tutor), it is always safe to state the help that you got. For example, if you had help from someone else in writing a component of your code, it is not plagiarism as long as you state (eg, as a comment in the code) who helped you in writing the method.

Classroom Policies

  • No eating, drinking, or smoking.
  • Respect classmates’ ideas, opinions, and questions.
  • No behaviour that prevents other students from learning.
  • You are welcome to visit the instructor’s office in his office hours.
  • Take good care of the laboratory facilities.

Points: 15
Prerequisites: XMUT 102
Duration:
Starts: semester 2
Campus: XMUT