INB371 Week 1 Lecture

7 Pages
Unlock Document

Malcolm Corney

INB371 Data Structures and Algorithms – Lecture 1 Lecture Overview – Introduction to the unit, data structures and algorithms, and C++ Malcolm Corney – Unit Coordinator/Lecturer [email protected] ph: 3138 1923, office: GP-S1042 Prereq knowledge sequence of statements (which statements run first), selection statements (if/else), repetition statements, variables, functions and methods, classes and libraries (object oriented programming basics, encapsulation,extension,etc), editing compilation and debugging Outcomes Use abstraction and encapsulation to design abstract data types (ADT's) Efficient implementation of data structures Efficient implementation of Algorithms Knowledge of algorithm analysis Analyse and solve programming problems by choosing appropriate data structures and algorithms Assessments Assignment 1 = 20% Assignment 2 = 30% Final Exam = 50% Classic algorithms binary search, insertion sort, selection sort, Efficiency PC hardware gets faster, memory gets cheaper, following Moore's Law. If you as a software developer can make software that uses less memory and resources to run, then you're doing the world a favour. Smartphones have limited resources, so efficiency is important especially in mobile applications. Some of the challenges which efficiency is helping: - Mapping the human genome. 3.3 million parts of DNA which need to be mapped, so efficient string comparison algorithms are required. - Expert systems capable of Natural Language, such as IBM's Watson, a computer able to play jeopardy. The computer has to be able to figure out the context of the natural language to search for I nformation on the internet and find the correct answer. – Could also be used for medicine, where a computer is given a list of symptoms and could find an answer. – Autonomous Vehicles, computers which can drive computers and control the speed, direction and decision making – GPS route finding, one of the classical algorithms in graph theory. Considering a bunch of locations with connections, trying to find the shortest path between two paths - “Djikstra'a Shortest Path” Travelling Salesman Problem Even some of the fastest computers in the world cannot compute something if the problem is too difficult, such as the Travelling Salesman problem. Given a list of cities and distances, try to find the shortest possible route that visits each city exactly once and returns to the city of origin. It's one of the most intensely studied optimisation problems. The simple way would to try each combination in order. Requires (n – 1)! / 2 routes to be calculated, which for 20 cities would be 60,822,550,204,416,000 different possibilities. On a simple laptop, you wouldn't be able to figure out the Travelling Salesman Problem for just 20 cities. Fortunately, better algorithms exist. The tour has been found for an 85,900 city instance. Introduction to C++ C++ is an extension of the languages C and SmallTalk. C was made for writing linux, and Smalltalk was one of the first object oriented languages, used in labs etc, and taught in QUT up until the 90's. Compilation process for C++ is taking a source file, running it through a compiler, which produces an object file. The object file is then linked with other object files and libraries which you may require for your program using a linker, and the linker produces an executable file. Java and C# run in a VM, which is converted to machine code with a Just In Time compiler, and then interacts with a Java runtime environment to interact with the low level computer. C++ uses MinGNU for Windows, and any assessment should be compiled using MinGNU. Microsoft C++ isn't standard C++, so using visual studio isn't advised. Importing libraries uses the #include command. The next line after a library include should be the location, which uses the code using namespace std;, as the two libraries (iostream and iomanip) are both in the std namespace. In C+ +, you have to declare everything before use, even functions. For example, int RaiseIntToPower(int n, int k); To print to screen, the command cout is used. << is used as a redirect, redirecting anything after it to the output stream. Endl is used to end a line. To create a loop, it is much like C#. for (int n = LOWER_LIMIT; n <= UPPER_LIMIT; n++) will take the value of LOWER_LIMIT and increase it by 1 until UPPER_LIMIT value is reached. Multi line commenting is done by /* and */, and single line commenting is //. Commenting should be included for the file, functions and amongst the code. Library inclusions always begin with #include, there is two styles, one with double quotes e.g. #include “stdio.h” which is for private libraries, or in angle brackets, which indicate a system library, e.g. #include . Majority of library inclusions will come from 'std' namespace. The example program imports functionality from std::iostream and std::iomanip, but when you include using namespace std; you don't have to type std before a command e.g. std.setw(3) you just type setw(3). After you import libraries, definitions that occur throughout the program are made, e.g. constant variables. Function prototypes are declared as well, you must declare a function before using it in C++. the main function should be the first function listed, as it's the function required to run your program. Parameter names are not required in the prototype of a function, e.g. you just use int functionname(int, int). Every program must contain a main function. It's the starting point for a program, so when main finishes, so does the program. In the example program, cout is used to display information to the screen. << puts information to the stream, endl is a stream manipulator. Because main is declared as a function returns int, it must have a return statement. If you return a 0, it indicates that the run was successful, and any other value indicates failure. Programs should be broken down into smaller units of work, giving the program structure and supporting reuse of code. Function definitions go together with function prototypes. Starting out, they will be in the same file, but as we look into abstract data types, we will separate definitions and prototypes, so that the header file provides the functionality. Functions should declare their own local variables. Parameters may also be passed into a function. Functions may also return one value to the caller of the function, although you can return more than one, which will be covered later. C++ is a strongly typed language, so variables have to have declared of a certain type and of a certain scope (which part of the program has access to it). Declaring a variable type namelist; type indicates the data type, namelistis a comma separated list of variable names. You can declare and add a value to a variable at same time e.g. int number = 0; NAMING CONVENTIONS Names for variables/functions/types/constants/c
More Less

Related notes for INB221

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.