More Related Content
Similar to Introduction to DSA..................... (20)
Recently uploaded (20)
Introduction to DSA.....................
- 1. Data Structures and Algorithms Lecture # 01 Topics: Problem Solving, Example Problems Engr. Dr. Asad Ullah
- 2. Prerequisites It is assumed that students entering this class have the following background: Fundamentals of Programming Object Oriented Programming
- 3. Course objectives This course develops students’ knowledge in data structures and the associated algorithms. Algorithms and data structures emphasizes the following topics: data structures, abstract data types, various sorting and searching algorithms, algorithm analysis and complexity, introduction to trees, binary trees, binary search tree operations. Introduction to graphs, depth first search and breadth first search, shortest paths, and topological sort and problem solving strategies. Divide a problem into its logical set of components. To provide knowledge in various data structures and algorithms. To introduce techniques for analyzing the efficiency of computer algorithms.
- 4. Textbook Nell Dale, Chip Weems, Tim Richards, ‘C++ Data Structures', Latest Edition Lecture Notes for Data Structures and Algorithms Revised each year by John Bullinaria Reference Books: Introduction to Data Structures in C by Ashok N. Kamthane. Data Structures and Algorithms by A.V. Aho, J.E.. Hopcroft, J.D. Ullman Data Structures Using C and C++ by Y. Langsam, M.J. Augenstein, A.M. Tenenbaum
- 5. Expected Assignments Write programs in several different languages Course project: to learn another language of your choice Includes a program, paper, and presentation Midterm Final exam Both exams are closed book
- 6. Grades 10%: Quizzes 10%: Programming homeworks 10%: Individual project and presentation 30%: Midterm 40%: Final exam In particular, you need to be conscious during class! Just having a pulse and being present is not sufficient
- 7. Late policy The late policy is 30% off for first 24 hours late, 50% off for the next 24 hours Assignments are not accepted after 48 hours from original due date Note that using your late day extends this calendar by 24 hours, so that you could turn the assignment in up to 72 hours after the original due date
- 8. Theory vs. Implementation This class focuses on both: Theory is covered by the textbook readings, lectures, and on the tests Implementation is covered by the lab/ homework assignments and the project You will need to do both to do well in the course You can’t slack off on the theory part! Thus, if you don’t keep up with the readings, you will end up with a poor grade in the course
- 9. Tentative schedule Already assigned to you people
- 10. Programming languages vs. compilers This is not a compilers course But we will be studying compilers in great detail The two fields are very closely linked You cannot understand one without understanding the other
- 11. Fairness I intend this course to be hard but fair If it is not being fair, please let me know and I will do my best to correct it If it is not being hard (or being to hard), also let me know
- 12. Upcoming readings I will try to give you the readings well in advance so you can plan accordingly See the course schedule as well
- 13. Keeping the class interesting Humor breaks Actually helps with attention span! Not surprisingly, most of it will be computer humor!
- 14. Agenda Problem Solving Problem Solving: A creative process The Problem-solving Process From Algorithms to Programs Algorithm – Examples Flowchart
- 15. Problem Solving Problem solving techniques Analyze the problem Outline the problem requirements Design steps (algorithm) to solve the problem Algorithm: Step-by-step problem-solving process Solution achieved in finite amount of time
- 16. Problem Solving: A creative process Problem solving techniques are not unique to Computer Science. The CS field has joined with other fields to try to solve problems better. Ideally, there should be an algorithm to find/develop algorithms. Problem solving remains an art!
- 18. Problem Idea Algorithm Program Informal Description Refinement Coding Testing & Debugging It’s not a linear process
- 19. From Algorithms to Programs Problem Program Algorithm: A sequence of instructions describing how to do a task (or process)
- 20. Problem - Example How to get out?
- 21. What is programming languages? A programming language is an artificial language that a computer understands. The language is made up of series of statements that fit together to form instructions. These instructions tell a computer what to do.
- 22. Continue …. There are many different programming languages, some more complicated and complex than others. Among the most popular languages are: Python Java C++ BASIC Scratch Different languages work in different ways. For example, in Python all instructions are written in lowercase, but in BASIC they tend to be written in uppercase.
- 23. Creating a program from an algorithm Consider this simple problem. A cricket match is offering discount tickets to anyone who is under 15. Decomposing this problem, gives this algorithm: find out how old the person is if the person is younger than 15 then say, “You are eligible for a discount ticket.” otherwise, say “You are not eligible for a discount ticket.”
- 24. Continue …. In pseudocode, the algorithm would look like this: OUTPUT "How old are you?" INPUT User inputs their age STORE the user's input in the age variable IF age < 15 THEN OUTPUT "You are eligible for a discount." ELSE OUTPUT "You are not eligible for a discount."
- 25. Continue …. In flow chart.
- 26. Programming languages are formal languages that define set of directions that is used to carry out different kind of output. Programming language contains set of instruction for computer. Thousands of languages has been contriving in field of computer. Programming language has two components - Syntax - Semantics
- 27. Programming Language Syntax English is a natural language. It has words, symbols and grammatical rules. A programming language also has words, symbols and rules of grammar. The grammatical rules are called syntax. Each programming language has a different set of syntax rules.
- 28. Why Are There So Many Programming Languages …….??? Why does some people speak French? Programming languages have evolved over time as better ways have been developed to design them. First programming languages were developed in the 1950s. Since then thousands of languages have been developed. Different programming languages are designed for different types of programs.
- 30. Conclusion With every passing year and month, the world of technology is extremely expending. So, programmers and web developers are in high demand because they have good knowledge of programming languages. And each of them are well defined in term of output, memory utilization and time complexity.
- 31. Algorithm A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer. For example "a basic algorithm for addition“. History: Abu Ja’far Muhammad ibn Musa al-Khorezmi (“from Khorezm”) Lived in Baghdad around 780 – 850 AD Chief mathematician in Khalif Al Mamun’s “House of Wisdom”
- 32. Computer Program VS Algorithm An algorithm is a strategy to solve a given problem, which you tend to think about before writing any code. Where as programming is the process of implementing that strategy. Algorithm is a set of instructions that solve a given problem. The computer may or (mostly) may not understand the language used for writing the algorithm (usually pseudo-code or English). Programming is transferring the content of the algorithm into a language the computer understands so that you can ask the computer to implement the algorithm.
- 33. Types of computer languages Two types of computer languages:- (1) Low level languages (2) High level languages High level programming languages: The languages that are close to programmer (Human beings). These languages were designed to make programming far easier and allow the programmer to program using them without having to know the details of internal structure of a particular computer.
- 34. Low level Computer Languages Low level programming languages: The language of hardware or the language that is near to hardware. Types of Low level programming languages: Machine Language Assembly Language Machine Language Language consists of 0’s and 1’s. Assembly Language The language consists mnemonics (symbols).
- 35. First Generation Programming Languages Introduced in the 1940's. Sometimes referred as Binary Language, Machine Language, Very Low Level Language, Machine Code or Object Code. It is a language made up of entirely 1s and 0s. Programmers have to design their code by hand then transfer it to a computer by using a punch card, punch tape or flicking switches. It is the only language a computer is capable of understanding without using a translation program. Close to machines. Modern day programmers still occasionally use machine level code, especially when programming lower level functions of the system, such as drivers, interfaces with firmware and hardware devices.
- 36. Continue… Advantages Machine language makes fast and efficient use of computer. It requires no translator to translate the code It is directly understood by the computer. Disadvantages All operations codes have to be remembered All memory addresses have to be remembered It is hard to amend or find errors in a program written in the machine language
- 37. Continue… An example of machine language (binary) for the text “Hello World”.
- 39. Second Generation Programming Languages Introduced in the 1950's. Sometimes referred as Assembly Language or Low Level Language. Programs are in the form of Alphanumeric Symbols (or Mnemonic Codes) instead of 0’s and l’s. These alphanumeric symbols can have maximum up to 5 letter combinations e.g. ADD for addition, SUB for subtraction, START LABEL etc. because of this feature it is also known as “Symbolic Programming Language”. Close to machine. Programs are translated into machine language using Assemblers. Not portable. Used in kernels and hardware driver, but more often find use in extremely intensive processing such as games, video editing, graphic manipulation/rendering.
- 40. Continue… Advantages Assembly language is easier to understand and use as compared to machine language It is easy to locate and correct errors. It is easily modified Disadvantages Like machine language, it is also machine dependent/specific Since it is machine dependent, the programmer also needs to understand the hardware
- 41. An example of Assembly language for the text “Hello World”
- 42. Examples of 2GL which are commonly in use today are: RISC (Reduced Instruction Set Computer) CISC (Complex Instruction Set Computer) X86 as that is what our embedded systems and desktop computers use.
- 43. Third Generation Of Programming Languages Introduced in the 1950's. Purpose of developing High-Level Languages was to enable people to write programs easily, in their own native language environment (English). These are Symbolic languages that use English words and/or mathematical symbols rather than mnemonic codes. Close to humans. Compiler (which converts the language into machine code automatically) was developed First compiled high level programming language : in 1952 for the Mark 1 computer at the University of Manchester. In 1954, FORTRAN was invented at IBM by John Backus. It was the first widely used high level general purpose programming language to have a functional implementation.
- 44. Continue… Advantages Easier to learn and understand than an assembly language as instructions (statements) that resemble human language or the standard notation of mathematics. Have less-rigid-rules, forms, and syntaxes, so the potential for error is reduced Are machine-independent programs therefore programs written in a high-level language do not have to be reprogrammed when a new computer is installed Programmers do not have to learn a new language for each computer they program
- 45. Continue… Disadvantages Less efficient than assembler language programs and require a greater amount of computer time for translation into machine instructions.
- 46. Fourth Generation Programming Languages 1970s through the 1990s. Also known as Very High Level Language or Non-Procedural Language. It is Application Specific. Close to natural language. Closer to the domain, Further from the machine. Fourth generation languages need approximately one tenth the number of statements that a high level languages needs to achieve the same results. Non-computer professionals can develop software.
- 47. Continue… Examples are 1. Query languages (SQL) 2. Report Programmer Generators (RPG by IBM) : created for punched card machines. 3. Applications generators 4. MATLAB 5. Some minicomputer applications e.g. PowerBuilder, FOCUS, Infotrieve-4GL, Progress 4GL etc.
- 48. Fifth Generation Programming Languages It is based on solving using constraints given to the program rather than using an algorithm written by a programmer. Introduced around 1990's. Very closely resembles human speech. Examples are Prolog, Mercury, OPS5, AI etc.
- 49. Continue… These languages are also designed to make the computer "smarter". Mainly used in artificial intelligence research. Natural languages already available for microcomputers include Clout, Q&A, and Savvy Retriever (for use with databases) and HAL (Human Access Language).
- 50. Example of AI (JARVIS)
- 52. Sophia Robot
- 54. Most Readable Programming Language Python
- 55. 1-55 Writability the ease with which a language can be used to create programs` Simplicity and orthogonality Few constructs, a small number of primitives, a small set of rules for combining them Support for abstraction The ability to define and use complex structures or operations in ways that allow details to be ignored Expressivity A set of relatively convenient “easy” ways of specifying operations Strength and number of operators and predefined functions
- 56. Reliability Type checking Testing for type errors Exception handling Intercept run-time errors and take corrective measures Writability and Readability Both readability and writability influence reliability A program is said to be reliable if it performs to its specifications under all conditions.
- 57. Cost (Money and Time) Training programmers to use the language Writing programs Compiling/ Executing programs “speed” Language implementation system: availability of free compilers Reliability: poor reliability leads to high costs Must have a online forum to answer the FAQs.
- 58. Other… Portability The ease with which programs can be moved from one implementation to anther Standard versions (C++ 98, C++11, C++2014, C++2017, C++20,….) Generality The applicability to a wide range of applications Well-definedness The completeness and precision of the language’s official definition
- 59. C++ Vs Java TOPIC C++ Java Memory Management Use of pointers, structures, union No use of pointers. Supports references, thread and interfaces. Libraries Comparatively available with low level functionalities Wide range of classes for various high level services Multiple Inheritance Provide both single and multiple inheritance Multiple inheritance is partially done through interfaces Operator Overloading Supports operator overloading It doesn’t support this feature Documentation comment C++ doesn’t support documentation comment. It supports documentation comment (/**.. */) for source code Program Handling Functions and variables can reside outside classes. Functions and variables reside only in classes, packages are used. Portability Platform dependent, must be recompiled for different platform Platform independent, byte code generated works on every OS. Thread Support No built-in support for threads, depends on libraries. It has built-in thread support.
- 60. DIFFERENCES B/W PROGRAMMING LANGUAGES
- 62. Flowchart Symbols – Cont. Start/End Oval symbol is used to represent the start or end of the flowchart. Process Rectangle symbol is used for process Start End A + B
- 63. Flowchart Symbols – Cont. Selection Diamond symbol is used to represent a selection step. It is also indicate a condition. Flow Lines Arrows symbol are used to represent the direction of flow in the flowchart. A > 5
- 64. Flowchart Example Add two numbers
- 66. Variables Are containers for values – places to store values. Variable as a portion of memory to store a determined value. Example: This jar can contain 10 cookies 50 grams of sugar 3 slices of cake etc. Values Variable
- 67. Restrictions on Variables Variables may be restricted to contain a specific type of value
- 68. 68 Instructions -- Application Some instructions can only be applied to a specific type of values or variables Examples:
- 70. Introduction Classes and class relationships are defined using UML Class diagrams These classes must be implemented Any OOP language can be used Visual Basic C# Java C++
- 71. 71 Objects A data type is used to declare a variable. A variable of a data type is also known as the instance or case of that data type. Each variable has unique name but each variable follows the rules of its data type. When a variable of a data type is declared, some space is reserved for it in the memory. A class is also like a data type. It is therefore used to declare variables or instances. The variables or instances of a class are called objects. A class may contain several data items and functions. Thus, the object of a class consists of both the data members and member functions of the class. The combining of both the data and the functions into one unit is called data encapsulation. An object represents data members of a class in the memory. Each object of class has unique name. The name of an object differentiates it from other objects of the same class. The values of data members of different objects may be different or same. The values of data members in an object are known as the state of the object. The functions in an object are called the member functions. They are also known as the them methods. The member functions are used to process and access data of the objects. Characteristics of Object (Identity, State & Behavior)
- 72. 72
- 73. 73
- 74. Key Terms (Programming Object) Programming objects are designed to mimic real-world objects Television set / DVD Objects have two important characteristics State: Current data about the object A dog has a name, color, etc… Behavior: Things the object can do A dog can bark, fetch, sit, etc.., The text boxes and buttons with which you are familiar are programming objects
- 75. Key Terms (Class) A class is a template or building block for an object We say that an object is an instance of a class We create several bicycles from the same template
- 76. Key Terms (Inheritance) Some classes have share characteristics with other classes Mountain bikes, road bikes, etc… all have shared characteristics OOP allows us to inherit state and behavior from other classes The parent classes is called the superclass The derived class is called the subclass
- 77. Key Terms (Interface) Here, we are not referring to user interface We refer to the methods and properties of a class that are exposed to the outside world In its most common form, an interface is a group of related methods with empty bodies Classes can then implement an interface
- 78. Benefits of OOP Modularity: Objects are generally independent of other objects Information hiding: The internal implementation of an object is hidden from the outside world Implementation vs. interface Code re-use: Objects can be reused by many other programs
- 79. Object Oriented Programming (OOP) OOP is methodology or paradigm ()ہنومن to design a program using class and object. OOP is paradigm that provides many concepts such as: Classes and objects Encapsulation (binding code and its data) etc. Inheritance Polymorphism Abstraction Overloading Class A Class is a collection of data and functions. The data items and functions are defined within the class. Functions are written to work upon the data items and each function has a unique relationship with data items of the class. Classes are defined to create user defined data types. These are similar to built-in data types available in all programming languages. Definition of data type does not create any space in the computer memory. When a variable of that data type is declared, a memory space is reserved for that variable. Similarly, when a class is defined, it does not occupy any space in the computer memory. It only defines the data items and the member function that can be used to work upon its data items. Thus, defining a class only specifies its data members and the relationship between the data items through it functions.
- 80. Defining a class A class is defined in a similar way as structure is defined. The keyword “class” is used to define the class. The general syntax to define a class is: class class_name { body of the class; } ; class is a keyword that is used to define a class. class_name It represents the name of the class.
- 81. body of classs The body of the class consist of the data items and the functions. These are called members of the class. These are written between braces. Semicolon ( ; ) The body of a class ends with semicolon. Members of a class A class contains data items and functions. These are called members of the class. The data items are called data members and the functions are called member functions. 1. Data Members The data items of a class are called data members of the class. For example, a class that has four integer type and two float type data items is declared as: class abc { int w , x , y , z; float a , b; } In the above class a, b, w, x, y and z are data members of the class “abc”.
- 82. 2. Member Functions The functions of a class that are defined to work on its data members are called member functions of the class. The member functions may be defined within the class or outside it.
- 83. For example: class xyz { private: int a , b , c; public: void getData(void) { cout<<E nter value of a, b and c”; cin>>a> >b>>c; } void printData(voi d) { cout<<“a= ”<<a<<endl; cout<<“b= ”<<b<<endl; cout<<“c= ”<<c<<endl; } } ;
- 84. For example: In this class, there are three data members and two member functions. The member functions are “getData” and “printData”. The “getData” function is used to input values into data members a, b and c. The “printData” function is used to print values of the data members on the computer screen.
- 85. INHERITANCE BASICS 1. Reusability is achieved by INHERITANCE 2. Java classes Can be Reused by extending a class. Extending an existing class is nothing but reusing properties of the existing classes. 3. The class whose properties are extended is known as super or base or parent class. 4. The class which extends the properties of super class is known as sub or derived or child class 5. A class can either extends another class or can implement an interface
- 86. Various Forms of Inheritance A B Single Inheritance A B Hierarchical Inheritance X A B C X A B C MultiLevel Inheritance A B C A B C A B C Multiple Inheritance NOT SUPPORTED BY JAVA A B C SUPPORTED BY JAVA
- 87. 87 Polymorphism (Many Types) The word polymorphism means having many forms (Polymorphism:– from the Greek “having multiple forms”) Typically, polymorphism occurs when there is a hierarchy of classes and they are related by inheritance A call to a member function will cause a different function to be executed depending on the type of object that invokes the function
- 88. 88 Polymorphism (Multiformity) The ability of objects to respond differently to the same message call The same invocation can produce “many forms” of results Also Known as “Late Binding” The same method name and signature can cause different actions to occur
- 89. 89 Shape class hierarchy Circle Right Triangle Isosceles Triangle Triangle Square Rectangle Shape Polymorphism Consider the following scenario:
- 90. 90 What if each of the shapes have a member function area()?
- 91. 91 Polymorphism is implemented in C++ using virtual functions A virtual function is a function in a base class that is declared using the keyword virtual Defining in a base class a virtual function, with another version in a derived class, signals to the compiler that we don't want static linkage for this function Virtual Function
Editor's Notes
- #18: ... the algorithm is our core concern. No program exists without an algorithm, but an algorithm without a program is
- #21: Statements: the smallest element of a programming languages which expresses a action to carried out. Instruction: a single action that can be performed by a computer processor.
- #31: Algorithms have a long history and the word can be traced back to the 9th century. At this time the Persian scientist, astronomer and mathematician Abdullah Muhammad bin Musa al-Khwarizmi, often cited as “The father of Algebra”, was indirect responsible for the creation of the term “Algorithm”.
- #32: Example An engineer plans for the house before construction, so a lot of effort is being put into it. Things like measuring the land, performing land test, deciding on different kind of materials to be used, drawing out architecture of house etc. are to be done before you start actual construction work. Once you start building house it is very difficult for you to alter things (doing changes in basement and you are in process of constructing top floor). This is the universal rule that is followed by all, designing will be done before producing actual product. Same logic is being used in programming, you can think of designing phase to be writing out algorithm, production phase to be programming using suitable language of your choice.
- #68: Let us think that I ask you to retain the number 5 in your mental memory, and then I ask you to memorize also the number 2 at the same time. You have just stored two different values in your memory. Now, if I ask you to add 1 to the first number I said, you should be retaining the numbers 6 (that is 5+1) and 2 in your memory. Values that we could now for example subtract and obtain 4 as result. The whole process that you have just done with your mental memory is a simile of what a computer can do with two variables. The same process can be expressed in C++ with the following instruction set: a = 5; b = 2; a = a + 1; result = a - b;