School of Computer Science
COMP SCI 2201/7201 Algorithm & Data Structure Analysis
Lecture 1 – Course Profile and Assessment Information
Copyright By PowCoder代写加微信 assignmentchef
Course Outline
• Week 1-6: Integer arithmetic, (Matrix) multiplications, Complexity proofs, Trees, Linear time sorting, order statistics
• Week 7-12: Hashing, Graph algorithms, Turing machines, Halting problem, Complexity class, NP- completeness
Assessment
Assessment
• This course has 2 components: – Writtenexamination60%
– Practicalassignments40%
• You are expected to participate in all activities, attend lectures and submit your assignments on time.
• Hurdle: You need at least 40% of the mark of the written examination to pass this course.
If you see an RP on your transcript, it means that your mark is not currently available. If you don’t know why, you should contact your course coordinator.
Minimum Performance
• On each component with a hurdle, you are required to achieve at least 40% of the marks allocated in the component.
• If your mark for any component with a hurdle is less than 40% of the allocated marks for that component, and your overall mark is greater than 45 F, your overall mark will be reduced to 45 F.
• To pass the course, you must obtain a passing mark overall and achieve at least 40% of the available marks in components with a hurdle.
Late submission policy
• You should hand your coursework in on time.
• If you hand in your work late, your mark will be capped, based on how many days late it is.
– up to 1 day late — mark reduced to 75%, marks below 75% not affected.
– up to 2 days late — mark reduced to 50%, marks below 50% not affected.
– up to 3 days late — mark reduced to 25%, marks below 25% not affected.
– More than 3 days late — mark is reduced to 0.
• If you handed in something on time, and it is worth more than something that you handed in late, you will get the higher mark.
• Hand in early!
Repeating Students
• Students who repeat a course are expected to attempt all of the aspects of the course again. This includes making fresh attempts at all coursework assessment items.
• You may apply to the course coordinator to have your previous work counted but this is not usually granted.
• Make sure that you attend all of the lectures, do all of the work and study hard for the exam – you don’t want to get stuck repeating the same course over and over.
Modified arrangements
Assignment extensions
• Extensions will not be granted for circumstances including minor ailments; travel, employment, family, customary, sport or leisure commitments; problems with balancing workloads; normal exam stress or anxiety.
• If you think your situation is exceptional, contact your course coordinator ASAP, who will then consult the Head of School.
• Students who deliberately submit false or fraudulent documentation may be referred to the Student Misconduct Tribunal.
• You will normally only receive an extension equivalent to
the number of days covered by your documentation.
Don’t expect to get an extra week because you lost a day.
Replacement exams
• Replacement exams will not be granted for circumstances including minor ailments; travel, employment, family, customary, sport or leisure commitments; problems with balancing workloads; normal exam stress or anxiety.
• Students granted a replacement exam are not eligible to sit the primary exam.
• Students who sit the primary exam will not be eligible to apply for a replacement exam unless a major issue arose during the exam.
• Students must make themselves available during the replacement exam period.
Replacement exams (cont.)
• Students will not be entitled to an additional assessment if they have already sat a replacement exam, i.e., no supps on supps.
• Students granted a deferred replacement exam will not be eligible to sit the primary exam or the replacement exam (only under exceptional circumstances will a deferred replacement exam be granted).
• The University must notify students of the outcome of their replacement exam applications within 3 business days (if you already sat the primary exam, do not bother applying for a replacement exam).
Replacement exams (cont.)
• Students who deliberately submit false or fraudulent documentation may be referred to the Student Misconduct Tribunal.
• For the full policy on Modified Arrangements, see: https://www.adelaide.edu.au/policies/3303
Additional/Replacement exam dates
• Go to the University Examinations Site for information on Additional/Replacement exams:
– http://www.adelaide.edu.au/student/exams/
Academic honesty policies
Academic Honesty Policies
• The University has strict policies prohibiting students from presenting other people’s work as their own, whether that of students or from outside the University.
• You may not copy code from another student or give another student your code to copy from, unless specifically authorised to do so by a staff member.
• You may not copy code from anywhere else, without permission.
• If caught, you may receive zero for the assignment, zero for the
course or be expelled.
• We don’t give you assignment work just to keep you busy, we do it to develop your understanding and ability to apply important techniques.
• If you don’t do the work yourself, you won’t be able to do it in the examination and you won’t be able to do it in the work force.
• Full policy available at the university webpages.
Violations to policy
• Plagiarism
– Usinganotherperson’sideas,designs,wordsorworkswithout
appropriate acknowledgment. • Collusion
– Anotherpersonassistingintheproductionofanassessment submission without the express requirement, or consent, or knowledge of the assessor.
Violations to policy
• Plagiarism
– Usinganotherperson’sideas,designs,wordsorworkswithout
appropriate acknowledgment. • Collusion
– Anotherpersonassistingintheproductionofanassessment submission without the express requirement, or consent, or knowledge of the assessor.
1. Do not submit any work or part thereof which is not yours.
2. Do not submit any work for which you have received unfair assistance.
• I had finished my assignment, and a classmate was asking for help. Since I am a kind person, I
– Gavetheclassmateacopyofmycode(orpartthereof).
• I had finished my assignment, and a classmate was asking for help. Since I am a kind person, I
– Gavetheclassmateacopyofmycode(orpartthereof).
– Postedmysolutiononanonlineforumforhis/herreference.
• I had finished my assignment, and a classmate was asking for help. Since I am a kind person, I
– Gavetheclassmateacopyofmycode(orpartthereof).
– Postedmysolutiononanonlineforumforhis/herreference.
– Allowedtheclassmatetohavealookatmycodeon paper/screen.
• I had finished my assignment, and a classmate was asking for help. Since I am a kind person, I
– Gavetheclassmateacopyofmycode(orpartthereof).
– Postedmysolutiononanonlineforumforhis/herreference.
– Allowedtheclassmatetohavealookatmycodeon paper/screen.
• I had finished my assignment, and a classmate was asking for help. Since I am a kind person, I
– Gaveafewhigh-leveltipstomyclassmate.
– Discussedhigh-levelconceptsregardingtheassignmentwithmy classmate.
• My good friend/housemate/brother/twin and I are taking the same course. We have always worked together. When doing the assignment, we
– Exchangedsolutionstoverify/compareouranswers.
• My good friend/housemate/brother/twin and I are taking the same course. We have always worked together. When doing the assignment, we
– Exchangedsolutionstoverify/compareouranswers.
– Dividedtheassignmentworkamongstourselvestospeedup progress.
• My good friend/housemate/brother/twin and I are taking the same course. We have always worked together. When doing the assignment, we
– Exchangedsolutionstoverify/compareouranswers.
– Dividedtheassignmentworkamongstourselvestospeedup
– Satside-by-sideandlookedateachother’sanswerswhendoing the assignment.
• My good friend/housemate/brother/twin and I are taking the same course. We have always worked together. When doing the assignment, we
– Exchangedsolutionstoverify/compareouranswers.
– Dividedtheassignmentworkamongstourselvestospeedup
– Satside-by-sideandlookedateachother’sanswerswhendoing the assignment.
• The assignment seems to be the same as the one given last year. I contacted my friend who took the course last year and got a copy of his solution.
• The assignment seemed to be similar to another given at a different university. So, I
– Copiedandsubmittedthemodelanswersavailableatthat university’s website.
– Tookpartsofthemodelanswersandintegratedthemintomy solution.
• I studied at a school/college/university where doing ______________ is acceptable. So I assumed doing this at The University of Adelaide is also acceptable.
How to avoid plagiarism/collusion
• If you get stuck, seek help from the lecturer, tutor or prac demonstrator rather than copying from someone else.
• Starting your work early will help you to avoid getting stuck at the last minute.
When in doubt, ask your lecturer.
Submission practicals / practical examinations
How to Submit your Practicals
• Go to https://cs.adelaide.edu.au/services/websubmission/
• There, find the directory name that you need to make in your
svn repository for each assignment
• Use secure shell to have external access to university’s computing resources:
ssh uss.cs.adelaide.edu.au
• Use svn commands to make the directory
• Upload (or make) your files in your directory
• Make sure your files are compiled with university’s compiler
• Go back to https://cs.adelaide.edu.au/services/websubmission/ and submit your work. (Don’t forget this!) and check feedback
• Get help from
– Your practical/workshop supervisors
– https://cs.adelaide.edu.au/current-students/handbook/external/
• You know what exactly the repository address of your assignment needs to be (from web-submission)
• Use svn commands to make that folder
svn mkdir –parents https://version-control.adelaide.edu.au/svn
/aXXXXXXX/what/ever/you/want -m “must have some comments”
– Either from your own terminal
– Or from the server, which you connect to by ssh. If you have windows, use Putty (a free ssh client) to connect to the server through ssh
• If you don’t have a working copy, check out this folder (or one of the parents) to get a fresh working copy of that
svn co https://version-control.adelaide.edu.au/svn /aXXXXXXX/what/ever/you/want localFolderAddress
– Either on your own computer
– Orontheserver(firstusesshtoconnect)
• If you already have a working copy of one of the parent folders,
– Eithermaketheassignmentfolder(s)locallyandaddthemby svn commands
• cd ExistingParentFolder
• svn add NewFolderName
• svn ci –m “comments”
– Orusesvncommandstomakethatfolder(s)ontheserver
• Then update your working copy folder. You will see the new directory in that
– cdExistingParentFolder – svn update
• Try not to have more than one working copy.
Code on the server
• If your working copy is on the server
– sshtoservereachtimeyouwanttoworkonit
– Gotoyourworkingcopyfolder
– Usevim(oranyotherterminal-basedtexteditor):
vim main.cpp
– g++-Wallmain.cpp
Let’s get started
Algorithm and Data Structure Analysis
Lecture 1: Introduction
Motivation
Why is this course important?
• Efficient data structures and algorithms are essential for successful computer applications
• We need efficient methods on how to store, manipulate data
• We need efficient algorithms to search them.
• Problems in computer science require efficient
algorithms.
Topic of this course:
Basic data structures and algorithms with focus on their analysis
Algorithm and Data Structure Analysis
Goals We want to have:
• Data structures that allow us to carry out operations as efficiently as possible
• Algorithms that solve problems as efficiently as possible.
Algorithm and Data Structure Analysis
Appetizer Sorting: Why should I care?
Which one do you prefer?
Algorithm and Data Structure Analysis
Efficiency
What’s our measure?
• Let n be the number of input elements (think of number of books)
• Measure time for operations on data structures and time to execute algorithms in dependence of n
• Consider orders of magnitude Algorithm and Data Structure Analysis
(Almost) Linear Runtime
Algorithm and Data Structure Analysis
Quadratic Runtime
Algorithm and Data Structure Analysis
Cubic Runtime
Algorithm and Data Structure Analysis
Exponential Runtime
Algorithm and Data Structure Analysis
Complexity
1.000.000.000
100.000.000
It’s great to have algorithms that run in linear time or time n logn.
Many important problems have algorithms whose runtime is bounded by a small polynomial (e. g. n2 or n3)
For a wide class of important problems there is most probably no algorithm that runs in polynomial time.
Algorithm and Data Structure Analysis
Asymptotic Behaviour
• Analysis of the growth rate of a function
• We measure runtime as a function of the input size n.
• Define complexity depending on the asymptotic behaviour.
• Want to have algorithms that solve a given problem and have low complexity.
Algorithm and Data Structure Analysis
Asymptotic Behavior
Algorithm and Data Structure Analysis
Algorithm and Data Structure Analysis
Landau Symbols
We want to measure computation times asymptotically
Mehlhorn, Sanders (page 21)
Algorithm and Data Structure Analysis
Right or Wrong
Right Right
Wrong Wrong
Algorithm and Data Structure Analysis
• Efficient data structures and algorithms are
crucial for successful computer applications. • Measure runtime as a function of the given
input size.
• Asymptotic behavior and complexity classes. • Reading: Mehlhorn & Sanders ch 2.1
Algorithm and Data Structure Analysis
Algorithm and Data Structure
Lecture 2: Integer Arithme;cs (Book Chapter 1)
Overview •School Method of Addi;on
•School Method of Mul;plica;on
Algorithm and Data Structure Analysis
What is an algorithm?
•An algorithm is a step by step list of direc;ons
that need to be followed to solve a problem.
•Algorithms are oJen used to describe how a
computer might solve a problem.
•A recipe can be a type of algorithm. It tells what ingredients are needed to make the dish and what steps to follow. If the recipe tells exactly what to do without too much confusion, then it is an algorithm.
From Wikipedia
Algorithm and Data Structure Analysis
Integer Arithme;cs
We want to have algorithms to carry out
•Addi;on
•Mul;plica;on of two numbers.
Recall what you have learned in school!
Algorithm and Data Structure Analysis
Example for Addi;on
a = 1289, b = 1342, B = 10
a 1289 b+ 1342
00110 02631
Algorithm and Data Structure Analysis
teach you one of them.
Representa;on
rithmetic on long integers is needed in areas such puting, and computer algebra and so an improved m
•Want to inves;gate integer arithme;cs
an intellectual gem but also useful for applications.
•Assume that integers are represented as digit analysis and basic algorithm engineering techniq
also see the interplay of theory and experiment.
•Base B number system, B>1
e assume that integers are represented as digit str
•Digits 0, 1, …, B-1
m, where B is an integer larger than one, there ar
string an−1an−2 …a1a0 represents the number represents ∑
0≤i ms with a small value of B are bPase 2, with digits 0
and base 16, with digits 0 to 15 (frequently written
Store in an array a of size n i=0 i acrognetarinbinagsnedsig,itsu. ch as 28, 216, 232, and 264, are also u
Algorithm and Data Structure Analysis
just basic shall
digit syste to 9, F). L
as c ultip
ings e dig
as 0 seful
“10101” in base 2 represents
1 24 +0 23 +1 22 +0
digit string a a …a a represents the num shall also see the interplay of theory and experime
h The Soviet stamp on this page shows Muhammad ib
systems with a small value of B are base 2, with We assume that integers are represented as d
entl e, th
to 9, and base 16, with digits 0 to 15 (frequ system, where B is an integer larger than on
8 16 32 dFig)i.tLstarrignegrabaseas, su.c.h.asa2 r,e2pre,se2nts, tahnedn2u
n−1 n−2 1 0
systems with a small value of B are base 2, wi
“10101” inbarseepr2esrenptrsesents 1·24+
to 9, and base 16, with digits 0 to 15 (frequent
F). 4Larger b3ases, suc2h as 28,1216, 232,0and 264, “924” in base 10 represents
1·2 +0·2 +1·2 +0·2 +1·2 =21
“10101” inbase2represents 1·24+0 •B=10
We assume that we have two primitive of three digits with a two-digit result (this i
represents
“924” in base 10 represents
The Soviet stamp on this page shows Muha
of three digits with a two-digit result (this is s
9·102 +2·101 +4·100 = 924
We assume that we have two primitive o
mately 780; died between 835 and 850), Per
Khorasan province of present-day Uzbekista
Algorithm and Data Structure Analysis
Primi;ve Opera;ons Assume that we have access to
•Addi;on of 3 digits with a 2 digits result (full adder)
1 Appetizer: Integer Arithmetics
•Mul;plica;on of 2 digits with 2 digits result
2 1 Appetizer: Integer Arithmetics 2 plication of two digits with a two-digit result. For exa
multiplication of two digits with a two-digit result.2 For example, in bas
Example (B=10): 3
Mul;plica;on
6 · 7 = 42 . 6 · 7 = 42 .
5 Addi;on 5
We shall measure the efficiency of our algorithms by the number of primitiv alltimonesaexseucruetedth. e efficiency of our algorithms by the numbe
Algorithm and Data Structure Analysis
We can artificially turn any -digit integer into an -digit integer for any
multi have
mple, e 10, w
e oper r of
nmm≥nb adding additional leading zeros. Concretely, “425” and “000425” represent the sam
tions executed.
y We can artificially turn any n-digit integer into an m-digit integer fo
Example for Addi;on
a = 1289, b = 1342, B = 10
a 1289 b+ 1342
00110 02631
Algorithm and Data Structure Analysis
denote the digits of b, and write b = (bn−1 …b0). 1.1
We We sim um the git is c ly,
School Method for Addi;on
all know how to add two integers a=(a …a ) and b=(b …b ). Input: Two integers a = (a ··n−·1a ) a0nd b = (b n−1···b0 )
an−1 … a1 a0
bn−1 … b1 b0 cn cn−1 … c1 0 sn sn−1 … s1 s0
first operand second operand carries sum
n 1 0 n 1 0
ply write one under the other with the least significant digits aligned, and s
Compute: s = a + b,
integers digitwise, carrying a single digit from one position to the next. This di
wheres=(s ···s )isann+1digitinteger.
alled a carry. The resnult will b0e an n + 1-digit integer s = (sn . . . s0 ). Graphical
erec toc isthesequenceofcarriesands=(s …s )isthesum.Wehavec = c · · · c is sequence of carries.
nn00 n0 0 1·B+si =ai+bi+ci for0≤i
Reviews
There are no reviews yet.