100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
Previously searched by you
Previously searched by you
logo
Ultimate DSA Study Guide with Visuals and Code Snippets $3.09   Add to cart
Quickly navigate to
Preview
  2.  
  3. IIT Guwahati
  4.  
  5. Cs205

Class notes

Ultimate DSA Study Guide with Visuals and Code Snippets
 1 view  0 purchase
  • Course
  • Cs205
  • Institution
  • IIT Guwahati

"A complete DSA study guide packed with detailed explanations, diagrams, and code snippets for all key topics like sorting algorithms, dynamic programming, and graph theory. Perfect for acing technical interviews!"

Preview 4 out of 106  pages

Document information

  • September 29, 2024
  • 106
  • 2024/2025
  • Class notes
  • Dr surya teja
  • All classes

Subjects

  • dsa notes
  • coding interview prep
  • data structures
  • algorithms
  • programming notes
  • coding practice
  • data structure concepts
  • sorting algo
  • sorting algorith
  • sorting algorith
  • sorting algorith
  • sorting algorithms

Written for

  • IIT Guwahati
  • Cs205
All documents for this subject (1)

Seller

avatar-seller
suryateja90149

Content preview

Contents
1 Introduction 1

1.1 What this book is, and what it isn’t . . . . . . . . . . . . . . . . 1

1.2 Assumed knowledge ......................... 1

1.2.1 Big Oh notation . . . . . . . . . . . . . . . . . . . . . . . 1

1.2.2 Imperative programming language . . . . . . . . . . . . . 3

1.2.3 Object oriented concepts . . . . . . . . . . . . . . . . . . 4

1.3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Tips for working through the examples . . . . . . . . . . . . . . . 6

1.5 Book outline ............................. 6

1.6 Testing ................................ 7

1.7 Where can I get the code? . . . . . . . . . . . . . . . . . . . . . . 7

1.8 Final messages ............................ 7

I Data Structures 8
2 Linked Lists 9

2.1 Singly Linked List .......................... 9

2.1.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.4 Traversing the list ...................... 12

2.1.5 Traversing the list in reverse order . . . . . . . . . . . . . 13

2.2 Doubly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.2 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.3 Reverse Traversal . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Binary Search Tree 19

3.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

,3.4 Finding the parent of a given node . . . . . . . . . . . . . . . . . 24

3.5 Attaining a reference to a node . . . . . . . . . . . . . . . . . . . 24

3.6 Finding the smallest and largest values in the binary search tree 25

3.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.7.1 Preorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26


3.7.2 Postorder . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.7.3 Inorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.7.4 Breadth First . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 Heap 32

4.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.3 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.4 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5 Sets 44

5.1 Unordered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.1.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.2 Ordered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6 Queues 48

6.1 A standard queue . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.2 Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.3 Double Ended Queue . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

7 AVL Tree 54

7.1 Tree Rotations ............................ 56

7.2 Tree Rebalancing . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

7.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

7.4 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

,II Algorithms 62
8 Sorting 63

8.1 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

8.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

8.3 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

8.4 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

8.5 Shell Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8.6 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

9 Numeric 72

9.1 Primality Test ............................ 72

9.2 Base conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

9.3 Attaining the greatest common denominator of two numbers . . 73

9.4 Computing the maximum value for a number of a specific base

consisting of N digits . . . . . . . . . . . . . . . . . . . . . . . . . 74

9.5 Factorial of a number . . . . . . . . . . . . . . . . . . . . . . . . 74

9.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

10 Searching 76

10.1 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

10.2 Probability Search . . . . . . . . . . . . . . . . . . . . . . . . . . 76

10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

11 Strings 79

11.1 Reversing the order of words in a sentence . . . . . . . . . . . . . 79

11.2 Detecting a palindrome ....................... 80

11.3 Counting the number of words in a string . . . . . . . . . . . . . 81

11.4 Determining the number of repeated words within a string . . . . 83

11.5 Determining the first matching character between two strings . . 84

11.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

A Algorithm Walkthrough 86

A.1 Iterative algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 86

A.2 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 88

A.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

, B Translation Walkthrough 91

B.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

C Recursive Vs. Iterative Solutions 93

C.1 Activation Records . . . . . . . . . . . . . . . . . . . . . . . . . . 94

C.2 Some problems are recursive in nature . . . . . . . . . . . . . . . 95

C.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

D Testing 97

D.1 What constitutes a unit test? . . . . . . . . . . . . . . . . . . . . 97

D.2 When should I write my tests? ................... 98

D.3 How seriously should I view my test suite? . . . . . . . . . . . . . 99

D.4 The three A’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

D.5 The structuring of tests ....................... 99

D.6 Code Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

D.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

E Symbol Definitions 101

VI Chapter 1

Introduction
1.1 What this book is, and what it isn’t
This book provides implementations of common and uncommon algorithms in
pseudocode which is language independent and provides for easy porting to most
imperative programming languages. It is not a definitive book on the theory of
data structures and algorithms.
For the most part this book presents implementations devised by the authors
themselves based on the concepts by which the respective algorithms are based
upon so it is more than possible that our implementations differ from those
considered the norm.
You should use this book alongside another on the same subject, but one that
contains formal proofs of the algorithms in question. In this book we use the
abstract big Oh notation to depict the run time complexity of algorithms so that
the book appeals to a larger audience.


1.2 Assumed knowledge
We have written this book with few assumptions of the reader, but some have been
necessary in order to keep the book as concise and approachable as possible. We
assume that the reader is familiar with the following:

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller suryateja90149. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for $3.09. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

76710 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling
$3.09
  • (0)
  Add to cart