obst.c

PHOTO

Thu Oct 17 2024 04:52:02 GMT+0000 (Coordinated Universal Time)

#include <stdio.h>
#include <limits.h>

#define MAX 100

int w[MAX][MAX], c[MAX][MAX], r[MAX][MAX];

void obst(int p[], int q[], int n);
int find(int c[][MAX], int r[][MAX], int i, int j);
void inorder(int r[][MAX], int i, int j, int p[]);

void obst(int p[], int q[], int n) {
    int i, j, m, k;

    // Initialize for empty and single keys
    for (i = 0; i <= n; i++) {
        w[i][i] = q[i];
        c[i][i] = 0;
        r[i][i] = 0;
    }

    // Initialize for trees with two keys
    for (i = 0; i < n; i++) {
        w[i][i + 1] = q[i] + q[i + 1] + p[i + 1];
        c[i][i + 1] = q[i] + q[i + 1] + p[i + 1];
        r[i][i + 1] = i + 1;
    }

    // Handle the last dummy key
    w[n][n] = q[n];
    c[n][n] = 0;
    r[n][n] = 0;

    // Dynamic programming to calculate costs
    for (m = 2; m <= n; m++) { // m is the size of the subtree
        for (i = 0; i <= n - m; i++) {
            j = m + i;
            w[i][j] = w[i][j - 1] + q[j] + p[j];
            k = find(c, r, i, j);
            c[i][j] = w[i][j] + c[i][k - 1] + c[k][j];
            r[i][j] = k;
        }
    }

    // Print cost and weight tables
    for (i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            printf("w[%d][%d] :%d\t", i, j, w[i][j]);
        }
        printf("\n");
        for (int j = 0; j <= n; j++) {
            printf("c[%d][%d] :%d\t", i, j, c[i][j]);
        }
        printf("\n");
    }

    // Print the maximum cost of the OBST
    printf("Maximum cost of the OBST: %d\n", c[0][n]);
}

int find(int c[][MAX], int r[][MAX], int i, int j) {
    int min = INT_MAX, l;
    for (int m = r[i][j - 1]; m <= r[i + 1][j]; m++) {
        if (c[i][m - 1] + c[m][j] < min) {
            min = c[i][m - 1] + c[m][j];
            l = m;
        }
    }
    return l;
}

void inorder(int r[][MAX], int i, int j, int p[]) {
    if (i < j) {
        int root = r[i][j];
        inorder(r, i, root - 1, p);  
        printf("%d ", p[root]);      // Visit root (keys are 1-indexed)
        inorder(r, root, j, p);       
    }
}

int main() {
    int p[MAX], q[MAX], i, n;
    printf("Enter size: ");
    scanf("%d", &n);

    printf("Enter probabilities of p (0 is assumed for p[0]):\n");
    for (i = 1; i <= n; i++) {
        printf("p[%d]: ", i);
        scanf("%d", &p[i]);
    }
    p[0] = 0; // Probability for p[0] (dummy key)

    printf("Enter probabilities of q (for q[0] to q[%d]):\n", n);
    for (i = 0; i <= n; i++) {
        printf("q[%d]: ", i);
        scanf("%d", &q[i]);
    }

    printf("Calculating OBST:\n");
    obst(p, q, n);

    printf("Inorder traversal of the OBST:\n");
    inorder(r, 0, n, p);
    printf("\n");

    return 0;
}

COPY

Save snippets that work from anywhere online with our extensions

Comments

ada

@signup

obst.c

#html #javascript #nodejs

How to Save HTML Form Data in JSON - Express

<form action="/new" method="post">
 
  <input name="title" type="text">
  <input name="description" type="text">
  <button type="submit">Submit Form</button>
 
</form>

> More steps

#javascript

Get URL and URL Parts in JavaScript

var newURL = window.location.protocol + "//" + window.location.host + "/" + window.location.pathname + window.location.search

#javascript

Add event listener to multiple buttons with the same class

    btns = document.getElementsByClassName("saveBtn");
    for (var i = 0; i < btns.length; i++) {
        btns[i].addEventListener("click", function () {
			//Add function here
        });
    }

#javascript

Replace Textarea with Codemirror editor

<link rel="stylesheet" type="text/css" href="plugin/codemirror/lib/codemirror.css">

<body>
	<textarea class="codemirror-textarea"></textarea>
</body>

<script>

$(document).ready(function(){
    var codeText = $(".codemirror-textarea")[0];
    var editor = CodeMirror.fromTextArea(codeText, {
        lineNumbers : true
    });
});

</script>

<script type="text/javascript" src="plugin/codemirror/lib/codemirror.js"></script>

#javascript #nodejs #commandline

HTTPS Redirect in Nodejs

npm install heroku-ssl-redirect

> More steps

#javascript #nodejs

Save to MongoDB without Duplicates Using Mongoose

var mongoose = require('mongoose');
var Schema = mongoose.Schema;

const exampleSchema = new Schema({
    title: { type: String , required: true},
    content: [{type: String}]
});


var Example = mongoose.model('Example', exampleSchema);
module.exports = Example;

> More steps

#html #javascript #jsfunctions #dom #dommanipulation

getAttribute() - how to get the value of any attribute of HTML element

<html>

<input id="contact" name="address">

<script>

    var x = document.getElementById("contact").getAttribute('name');

</script>

</html>

#javascript

Full Stack Developer

function full_stack_developer() {
    full_stack_developer();
}

#javascript #javascript #functions #parameters

Required Parameters for Functions in JavaScript

 const isRequired = () => { throw new Error('param is required'); };

const hello = (name = isRequired()) => { console.log(`hello ${name}`) };

// These will throw errors
hello();
hello(undefined);

// These will not
hello(null);
hello('David');
The idea here is that it uses default parameters, like how the b parameter here has a default if you don’t send it anything:
function multiply(a, b = 1) {
  return a * b;
}

#javascript

3 Ways To Detect Selenium Bots Using Javascript - CodingTutz

if (navigator.webdriver) {
    document.body.innerHTML = "This is a Bot";
}

#html #jquery #css #navbar

Underline active navbar link

// in css:
/* Display line under clicked navbar link */
.active {
  text-decoration-line: underline !important;
  text-decoration-thickness: 2px !important;
  color: rgb(20, 19, 19);
}

//in html: 
    <script src="https://ajax.googleapis.com/ajax/libs/jquery/3.5.1/jquery.min.js"></script>

    <script>
      $(document).ready(function () {
        // Underline to remain in navbar after click using URL
        jQuery(function ($) {
          var path = window.location.href; // because the 'href' property of the DOM element is the absolute path
          $('.nav-link').each(function () {
            if (this.href === path) {
              $(this).addClass('active');
            }
          });
        });
      });
    </script>

//Note class in link should be nav-link

#javascript

Copy Text to Clipboard with Line Breaks

function copyToClipboard(){

    var codeToBeCopied = document.getElementById('code-snippet').innerText;
    var emptyArea = document.createElement('TEXTAREA');
    emptyArea.innerHTML = codeToBeCopied;
    const parentElement = document.getElementById('post-title');
    parentElement.appendChild(emptyArea);

    emptyArea.select();
    document.execCommand('copy');

    parentElement.removeChild(emptyArea);
    M.toast({html: 'Code copied to clipboard'})

    }

#javascript #promises #howto

How to Get the Domain From A URL Using Javascript

var url = "http://scratch99.com/web-development/javascript/";
var urlParts = url.replace('http://','').replace('https://','').split(/[/?#]/);
var domain = urlParts[0];

#javascript

Mapping an Object

const object1 = {
  a: 'somestring',
  b: 42
};

for (let [key, value] of Object.entries(object1)) {
  console.log(`${key}: ${value}`);
}

#javascript #jquery

jQuery.post() - AJAX for post requests

$.ajax({
  type: "POST",
  url: url,
  data: data,
  success: success,
  dataType: dataType
});

obst.c

Save snippets that work from anywhere online with our extensions

Comments

More like this

ada

Browse more snippets >>

obst.c

Save snippets that work from anywhere online with our extensions

Comments

More like this

ada

Browse more snippets >>

Embed code snippet